#include #include #include #include #include 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;

}[](``********<u><u>****</u></u>********``)