Problem Description

You are currently in a matrix of size $m$ rows (row numbers start from $0$ and go up to $m-1$) and $n$ columns (column numbers start from $0$ and go up to $n-1$). Your initial position is $(0,0)$. ($(r,c)$ denotes the position in the $r$-th row and $c$-th column of the matrix)

You need to reach the position $(m-1,n-1)$. This matrix is quite magical—there are arrows on some of the cells. The arrows can only have four directions: North (up), East (right), South (down), and West (left). These arrows are distributed throughout the matrix, forming an arrow matrix.

When you are at a certain position, if this position is outside the rectangle (top-left corner $(0,0)$, bottom-right corner $(m-1,n-1)$) or there is no arrow at this position, you will stay here forever and never reach the destination. If there is an arrow here, you will move one cell in the direction of the arrow.

However, you may not necessarily find a path from $(0,0)$ to $(m-1,n-1)$ on the initial arrow matrix. To find such a path, you can rotate an arrow in the arrow matrix clockwise by $90$ degrees once. Through several rotations, you might find a path.

Determine whether it is possible to obtain a path from $(0,0)$ to $(m-1,n-1)$ by rotating arrows, and if so, find the minimum number of rotations required.

Input Format

The first line contains two integers $m, n$, representing the size of the matrix.

The next $m$ lines, each containing a string of length $n$, represent the arrow information for that row in the arrow matrix. The string can only contain five characters: W, E, N, S, X. They respectively denote: West, East, North, South, and no arrow.

Output Format

If there is no way to find a path through rotations, output -1.

If there is a way, output an integer representing the minimum number of rotations needed.

Sample Input and Output

Sample Input #1

3 3
EES
SSW
ESX

Sample Output #1

3

Sample Input #2

3 3
EES
SSW
EEX

Sample Output #2

0

Sample Input #3

3 4
EXES
WSNS
XNNX

Sample Output #3

4

Notes

Sample Explanation

Sample 1 Explanation
- A possible solution is to rotate the W at position $(1,2)$ three times to become S.

Sample 2 Explanation
- No rotations are needed.

Sample 3 Explanation
- Rotate once at $(0,0)$, twice at $(1,0)$, and once at $(2,1)$.

Data Size and Constraints

This problem uses multiple test cases bundled together, with a total of 5 subtasks.

• Subtask 1 (10 points): $m=1$, and the input character matrix only contains E or X.
• Subtask 2 (12 points): $m=1$.
• Subtask 3 (12 points): $n=m=3$.
• Subtask 4 (16 points): $m=2$.
• Subtask 5 (50 points): No special restrictions.

For all test cases, it is guaranteed that $1 \le m, n \le 500$.

Notes

Original problem from: eJOI2019 Problem F Awesome Arrowland Adventure

Problem statement translation: @Wallace (If you find this translation unsatisfactory, feel free to provide a new one)

见题面 Input 部分

见题面 Output 部分