P2689 East, South, West, North

Given the coordinates of the start and end points, and the wind direction (east, south, west, north) at each of the next $T$ time steps, you may either move $1$ unit with the wind or stay in place at each time step. Find the **minimum number of moves** needed to reach the destination. The coordinate system is the Cartesian plane, where the positive $x$-axis points east and the positive $y$-axis points north. If it is impossible to reach the destination, output $-1$.

The first line contains two positive integers $x_1, y_1$, representing Xiaoming’s current position. The second line contains two positive integers $x_2, y_2$, representing the position Xiaoming wants to reach. The third line contains an integer $T$, representing $T$ time steps. From line $4$ to line $T+3$, each line contains one character representing the wind direction, i.e., the first letter of the English words for east ($\verb!E!$), south ($\verb!S!$), west ($\verb!W!$), and north ($\verb!N!$).

Output a single integer, the minimum number of moves.

Sample Explanation - Sample $1$: Move one step east, then one step north. - Samples $2$ and $3$: Impossible to reach. Constraints For all testdata, $1 \le T \le 50$. Translated by ChatGPT 5