Strange Strelyandsk Journey
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) and n columns (numbered from 0 to 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, 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, 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 ≤ n, m ≤ 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.
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.