Description

You are now in a matrix of size $m$ rows (rows are numbered from $0$, from top to bottom up to $m-1$) and $n$ columns (columns are numbered from $0$, from left to right up to $n-1$). Your initial position is $(0,0)$. ($(r,c)$ denotes the cell in row $r$ and column $c$ of the matrix.)

You need to reach position $(m-1,n-1)$. This matrix is very magical: some cells contain an arrow. An arrow can only point in one of four directions: North (up), East (right), South (down), or West (left). These arrows are spread across the whole matrix, forming an arrow matrix.

When you are at some 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 in this cell, then you will stay there forever and will never reach the destination. If there is an arrow here, then you will move one cell in the direction of the arrow.

However, it is obvious that you may not be able to find a path from $(0,0)$ to $(m-1,n-1)$ in the initial arrow matrix. To find such a path, each time you may rotate one arrow in the arrow matrix by $90$ degrees clockwise. After several rotations, you might be able to find a path.

Determine whether it is possible to obtain a path from $(0,0)$ to $(m-1,n-1)$ by rotations. If it is possible, output the minimum number of rotations needed.

Input Format

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

The next $m$ lines each contain a string of length $n$, describing the arrows in that row of the arrow matrix. The string contains only $5$ kinds of characters: W, E, N, S, X. They represent: West, East, North, South, and no arrow, respectively.

Output Format

If there is no rotation plan that can produce a valid path, output -1.

Otherwise, output one integer, the minimum number of rotations required.

3 3
EES
SSW
ESX

3

3 3
EES
SSW
EEX

0

3 4
EXES
WSNS
XNNX

4

Hint

Sample Explanation

[Sample 1 Explanation]

• One feasible solution is to rotate the W at position $(1,2)$ three times to make it become S.

[Sample 2 Explanation]

• No rotation is needed.

[Sample 3 Explanation]

• Rotate once at $(0,0)$, rotate twice at $(1,0)$, and rotate once at $(2,1)$.

Constraints

This problem uses bundled testdata, with a total of $5$ subtasks.

• Subtask 1 (10 points): $m=1$, and the input character matrix contains only 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

The original problem is from: eJOI2019 Problem F Awesome Arrowland Adventure.

Statement translation: @_Wallace_ (if you find this translation confusing, feel free to provide a new one).

Translated by ChatGPT 5