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

编程题

远航

时间限制: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 <string>
#include <vector>
#include <numeric>
#include <cmath>

using namespace std;

// 预计算的风位移
long long prefix_wind_x[100005];
long long prefix_wind_y[100005];
long long cycle_x, cycle_y;
int n;
long long dx, dy;

/**
 * @brief 检查 K 天是否足够
 * @param K 天数
 * @return true 如果 K 天可能到达，否则 false
 */
bool check(long long K) {
    if (K == 0) return (dx == 0 && dy == 0);

    long long num_cycles = K / n;
    long long remaining_days = K % n;

    long long wind_x = num_cycles * cycle_x;
    long long wind_y = num_cycles * cycle_y;

    if (remaining_days > 0) {
        wind_x += prefix_wind_x[remaining_days - 1];
        wind_y += prefix_wind_y[remaining_days - 1];
    }

    long long required_ship_x = dx - wind_x;
    long long required_ship_y = dy - wind_y;

    long long required_dist = abs(required_ship_x) + abs(required_ship_y);

    // 约束 1: 距离足够
    // 约束 2: 奇偶性相同 (K % 2 == required_dist % 2)
    // 我们的主函数已经预先检查了奇偶性，这里 K 和 required_dist 奇偶性自动相同
    return K >= required_dist;
}

long long solve() {
    long long sx, sy, ex, ey;
    cin >> sx >> sy >> ex >> ey;
    string wind_s;
    cin >> n >> wind_s;

    dx = ex - sx;
    dy = ey - sy;

    // 关键奇偶性预检查
    // f(0) = 0 - (abs(dx) + abs(dy))
    // f(K) 必须为偶数，且 f(K) 的奇偶性 = f(0) 的奇偶性
    // 因此 f(0) 必须为偶数，即 abs(dx) + abs(dy) 必须为偶数
    if ((abs(dx) + abs(dy)) % 2 != 0) {
        return -1;
    }

    // 预处理风的前缀和
    prefix_wind_x[0] = 0;
    prefix_wind_y[0] = 0;

    for (int i = 0; i < n; ++i) {
        // (i > 0) 的情况
        if (i > 0) {
            prefix_wind_x[i] = prefix_wind_x[i - 1];
            prefix_wind_y[i] = prefix_wind_y[i - 1];
        }
        
        // (i = 0) 的情况，从 (0,0) 开始
        if (i == 0) {
             prefix_wind_x[0] = 0;
             prefix_wind_y[0] = 0;
        }

        if (wind_s[i] == 'U') prefix_wind_y[i]++;
        else if (wind_s[i] == 'D')