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

// 定义状态结构体:当前坐标(x,y)、当前时刻t、已走步数step
struct State {
    int x, y;
    int t;
    int step;
};

int main() {
    // 输入起点、终点、时刻数
    int sx, sy, ex, ey, T;
    cin >> sx >> sy;
    cin >> ex >> ey;
    cin >> T;
    
    // 存储每个时刻的风向对应的坐标偏移
    vector<pair<int, int>> dirs(T);
    for (int i = 0; i < T; i++) {
        char d;
        cin >> d;
        // 严格按照题目提示映射风向:
        // E东→x+1;S南→y-1;W西→x-1;N北(从北刮来)→向南走→y-1
        if (d == 'E') {
            dirs[i] = {1, 0};
        } else if (d == 'S') {
            dirs[i] = {0, -1};
        } else if (d == 'W') {
            dirs[i] = {-1, 0};
        } else if (d == 'N') { // 题目核心提示:N风向南走
            dirs[i] = {0, -1};
        }
    }
    
    // BFS相关初始化
    queue<State> q;
    // 标记访问状态:visited[x][y][t] 表示在时刻t到达(x,y)是否已访问
    // 坐标范围:考虑到T最大50,坐标偏移最多±50,所以范围设为-100~200足够
    bool visited[300][300][60];
    memset(visited, false, sizeof(visited));
    
    // 初始状态:起点、时刻0、步数0
    q.push({sx, sy, 0, 0});
    visited[sx + 100][sy + 100][0] = true; // 加偏移避免负数下标
    
    int min_step = -1; // 默认无法到达
    
    // BFS核心逻辑
    while (!q.empty()) {
        State curr = q.front();
        q.pop();
        
        // 终止条件1:已到达终点,记录步数并退出(BFS第一个找到的就是最短步数)
        if (curr.x == ex && curr.y == ey) {
            min_step = curr.step;
            break;
        }
        
        // 终止条件2:所有时刻都用完了,跳过
        if (curr.t >= T) {
            continue;
        }
        
        // 选项1:当前时刻停留原地
        if (!visited[curr.x + 100][curr.y + 100][curr.t + 1]) {
            visited[curr.x + 100][curr.y + 100][curr.t + 1] = true;
            q.push({curr.x, curr.y, curr.t + 1, curr.step});
        }
        
        // 选项2:顺着当前时刻的风向移动
        int dx = dirs[curr.t].first;
        int dy = dirs[curr.t].second;
        int nx = curr.x + dx;
        int ny = curr.y + dy;
        
        if (!visited[nx + 100][ny + 100][curr.t + 1]) {
            visited[nx + 100][ny + 100][curr.t + 1] = true;
            q.push({nx, ny, curr.t + 1, curr.step + 1});
        }
    }
    
    // 输出结果
    cout << min_step << endl;
    
    return 0;
}

0 条评论

目前还没有评论...

信息

ID
249
时间
1000ms
内存
256MiB
难度
9
标签
递交数
25
已通过
3
上传者