Strange Strelyandsk Journey#9048

Strange Strelyandsk Journey

1 secondo

128 megabyte

Molto facile

The European Junior Informatics Olympiad in the year 2542 is being hosted in Arrowland, a country shaped like a grid with $m$ rows (numbered from $0$ to $m - 1$ m - 1) and $n$ columns (numbered from $0$ to $n - 1$ n - 1). Each cell in this grid represents a city. The cell at position ( $r$ , $c$ ) is located in row $r$ and column $c$ . The dormitory where participants stay is situated at cell ( $0$ , $0$ ), while the competition hall is located at cell ( $m - 1$ m - 1, $n - 1$ n - 1).

Arrowland is unique because some cities have large arrows that can be rotated $90$ degrees clockwise in one operation. Initially, each arrow points in one of four directions: north, east, south, or west. The Olympiad organizers want to utilize this feature to guide participants.

Participants will follow the arrows, moving from one city to the next in the direction indicated by the arrow. If they arrive at a city without an arrow or move beyond the boundaries of Arrowland, they will get lost and miss the Olympiad. The organizers aim to ensure that all participants can safely travel from the dormitory (cell ( $0$ , $0$ )) to the competition hall (cell ( $m - 1$ m - 1, $n - 1$ n - 1)). To accomplish this, they may need to rotate some arrows. Your task is to determine the minimum number of rotations required to achieve this goal, or to report if it is impossible for participants to reach the competition hall regardless of arrow orientation.

Input

The first line contains two integers $m$ and $n$ ( $1 \leq n, m \leq 500$ 1 \leq n, m \leq 500) representing the number of rows and columns. The following $m$ lines each contain $n$ characters, indicating the initial direction of the arrows (N for north, E for east, S for south, W for west, X for no arrow). The last character of the last row (i.e., the competition hall) will always be X. The symbol N indicates the direction "up", E means "right", S means "down", and W means "left". Each cell contains one of the symbols: N, E, S, W, X.

Output

Output the minimum number of arrow rotations needed by the organizers. If no solution exists, output $- 1$ .

Esempi

Esempio 1

Esempio 2

Esempio 3

Nota

Explanation for the first example: The optimal solution is to change the W in cell ( $1$ , $2$ ) to S by rotating the arrow three times.

Explanation for the second example: No changes are necessary; the participants can reach the competition hall as is.

Explanation for the third example: Rotate the arrow in cell ( $0$ , $0$ ) once to S, the arrow in cell ( $1$ , $0$ ) twice to E, and the arrow in cell ( $2$ , $1$ ) once to E.