Sail

题意翻译

# 题意 从($s_x$,$s_y$)驶向($e_x$,$e_y$)给出时刻总数t,有四种风向东南西北($E$,$S$,$W$,$N$),每一时刻给出一种风向,$E$$-$>$x$坐标+1,$S$$-$>y坐标-1,$W$$-$>x坐标-1,$N$$-$>y坐标+1,可以选择随风移动也可以选择停留(但都会经过1个时刻)求到达终点所需要的最小时刻。 ## 输入格式 第一行输入$t$,$s_x$,$s_y$,$e_x$,$e_y$。 第二行输入$t$个字符表示每一时刻的风向. ## 输出格式 若能达到输出一个整数表示最短时刻, 若不能达到则输出"-1"

题目描述

The polar bears are going fishing. They plan to sail from $ (s_{x},s_{y}) $ to $ (e_{x},e_{y}) $ . However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at $ (x,y) $ . - If the wind blows to the east, the boat will move to $ (x+1,y) $ . - If the wind blows to the south, the boat will move to $ (x,y-1) $ . - If the wind blows to the west, the boat will move to $ (x-1,y) $ . - If the wind blows to the north, the boat will move to $ (x,y+1) $ . Alternatively, they can hold the boat by the anchor. In this case, the boat stays at $ (x,y) $ . Given the wind direction for $ t $ seconds, what is the earliest time they sail to $ (e_{x},e_{y}) $ ?

输入输出格式

输入格式

The first line contains five integers $ t,s_{x},s_{y},e_{x},e_{y} $ $ (1<=t<=10^{5},-10^{9}<=s_{x},s_{y},e_{x},e_{y}<=10^{9}) $ . The starting location and the ending location will be different. The second line contains $ t $ characters, the $ i $ -th character is the wind blowing direction at the $ i $ -th second. It will be one of the four possibilities: "E" (east), "S" (south), "W" (west) and "N" (north).

输出格式

If they can reach $ (e_{x},e_{y}) $ within $ t $ seconds, print the earliest time they can achieve it. Otherwise, print "-1" (without quotes).

输入输出样例

输入样例 #1

5 0 0 1 1
SESNW

输出样例 #1

4

输入样例 #2

10 5 3 3 6
NENSWESNEE

输出样例 #2

-1

说明

In the first sample, they can stay at seconds $ 1 $ , $ 3 $ , and move at seconds $ 2 $ , $ 4 $ . In the second sample, they cannot sail to the destination.