시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 512 MB16121275.000%

문제

European Junior Olympiad in Informatics 2542 is held in Arrowland. Arrowland is shaped like a grid with m rows (numbered 0 through m-1) and n columns (numbered 0 through n-1), where each cell represents a city. Let (r, c) denote the cell in row r and column c. The contestants are accommodated in the cell (0, 0), and the competition hall is in the cell (m-1, n-1).

A strange tourist attraction of Arrowland is that some cities have giant arrows. Even stranger, these arrows can only be rotated clockwise by 90 degrees at a time. Each arrow initially points to either North, East, South, or West. Because of the host country's name, the EJOI organizers want to make use of the arrows.

The contestants will blindly follow the arrows, regardless of their current position. From each city, they simply move to the adjacent city pointed to by the arrow. If they enter a city with no arrow or if they leave Arrowland, they will just stay there and will never reach the competition hall. Since the EJOI organizers want the contestants to arrive to the hall from their accomodation (cell (0, 0)), they might have to rotate some arrows. Help them determine the minimum number of rotations required to achieve their goal, or tell them that the contestants cannot reach the hall, regardless of the arrows' orientation.

입력

The first line contains two integers, m and n, denoting the number of rows and columns, respectively. The next m lines each contain n characters denoting the initial direction of the arrows (N – north, E – east, S – south, W – west, X – no arrow in this cell). The last character in the last row (i.e., the character corresponding to the competition hall) is guaranteed to be X.

In the input matrix, the directions North, East, South, and West have the same meaning as they do on a standard map. Therefore, the character N means "upwards", E means "to the right", S means "downwards", and W means "to the left".

출력

Output the minimum number of rotations that EJOI organizers have to perform. Output -1 if their task is impossible.

제한

• 1 ≤ m ≤ 500
• 1 ≤ n ≤ 500
• Each cell contains one of these characters: N, E, S, W, X.

서브태스크

번호 배점 제한
1 10

m = 1; each cell contains either a character E or a character X.

2 12

m = 1.

3 12

m = n = 3.

4 16

m = 2.

5 50

예제 입력 1

3 3
EES
SSW
ESX


예제 출력 1

3


In this case, one possible optimal solution is to change W in the cell (1, 2) to S by rotating the arrow three times.

예제 입력 2

3 3
EES
SSW
EEX


예제 출력 2

0


Here, the EJOI organizers don't have to change anything for the contestants to arrive to the competition hall.

예제 입력 3

3 4
EXES
WSNS
XNNX


예제 출력 3

4


Rotate the arrow in the cell (0, 0) once (to obtain S), the arrow in the cell (1, 0) twice (to obtain E), and the arrow in the cell (2, 1) once (to obtain E).

채점 및 기타 정보

• 예제는 채점하지 않는다.