Awesome Arrowland Adventure
Time limit2sMemory limit512 MB
Each grid cell has a rotatable arrow or none; rotate arrows clockwise (90 degrees each) so a walker starting at (0,0) follows arrows to reach (m-1,n-1), minimizing rotations.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Implementation, Matrix
- Solved
- No attempts yet
Problem
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 at the hall from their accommodation (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.
Input
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 for north, E for east, S for south, W for west, X for 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
Output the minimum number of rotations that the EJOI organizers have to perform. Output -1 if their task is impossible.
Constraints
- 1 ≤ m ≤ 500
- 1 ≤ n ≤ 500
- Each cell contains one of these characters:
N,E,S,W,X.