烽火通信软件研发(通用)笔试 9-16

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

编程题

远航

时间限制:5000MS

内存限制:786432KB

题目描述:

船队要远航之前会先探测航行时的风向。根据探测队的情报，这个地区的风是周期性无限循环的,每个周期持续n天。同时，风力都处处相同，只有每天的风向不同:

U:表示风会把一个物体从(x,y)吹向(x,y+1);

D:表示风会把一个物体从(x,y)吹向(x,y-1);

L:表示风会把一个物体从(x,y)吹向(x-1,y);

R:表示风会把一个物体从(x,y)吹向(x+1,y);

有时候船队会利用或者抵抗风的作用。每一天，船队可以选择一个方向进行航行，向该方向前进一格。船队自己的作用与风的作用会叠加，例如船队在(x,y)向上(U)开，而此时风向为L时，船队会从(x,y)到达(x-1,y+1).

船队从(sx,sy)出发，目的地是(ex,ey)。在航行之前，身为船长的你需要知道最快需要多少天才能到达目的地，或者无法到达。假设这片海域无限大。

输入描述

第一行一个正整数T,表示数据组数。

对于每一组数据,第一行四个整数sx,sy,ex,ey;

第二行一个正整数n;

第三行一个长度为n的仅包含UDLR四种字符的字符串，表示一个周期内每天的风向。

对于100%的数据，1≤n≤10^5,0<sy,sy,ex,ey<10^9,1≤T≤5，(sx,sy)≠(ex,ey)

输出描述

对于每一组数据，如果船队能够到达目的地,输出最少需要的天数;否则,输出-1。

样例输入

2

0 0 3 5

3

URU

0 0 3 3

1

D

样例输出

4

-1

提示

对于样例一，船的操作为RRUU

坐标变化为(0,0)→(1,1)→(3,1)→(3,3)→(3,5)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int solve(int sx, int sy, int ex, int ey, int n, string wind) {
    int dx = ex - sx, dy = ey - sy;
    int base_days = abs(dx) + abs(dy);
    vector<int> wind_effect_x(n + 1, 0), wind_effect_y(n + 1, 0);
    
    for (int i = 1; i <= n; ++i) {
        wind_effect_x[i] = wind_effect_x[i - 1];
        wind_effect_y[i] = wind_effect_y[i - 1];
        switch (wind[i - 1]) {
            case 'U': wind_effect_y[i]++; break;
            case 'D': wind_effect_y[i]--; break;
            case 'L': wind_effect_x[i]--; break;
            case 'R': wind_effect_x[i]++; break;
        }
    }

    for (int days = 0; days < base_days + n; ++days) {
        int cycle = days / n;
        int cur_day = days % n;
        
        int add_x = cycle * wind_effect_x[n] + wind_effect_x[cur_day + 1];
        int add_y = cycle * wind_effect_y[n] + wind_effect_y[cur_day + 1];

        if (abs(dx - add_x) + abs(dy - add_y) <= days) return days;
    }
    
    return -1;
}

int main() {
    int T, sx, sy, ex, ey, n;
    cin >> T;
    while (T--) {
        cin >> sx >> sy >> e