Maze is a grid of MxN cells, each cell has 4 doors that allow you to move into one of the neighbouring cells. At any point of time only one of them is open. Doors are one-way, meaning that if you can move from cell A to B it does not necessarily mean that you can move from B to A at the same point of time. The initial arrangement of doors is given, after one unit of time has passed the currently open door closes and the one that is 90 degrees clockwise from it opens.
There are K treasure chests that you are supposed to pick up and their coordinates are given. You can only move from one cell to another if the corresponding door is open. Moving from cell to cell takes one unit of time, but you may have to wait for the specific door to open.
You start at the top left corner (1,1), have to pick up all treasure chests and exit the maze at the bottom right square (M,N). You can enter the square (M,N) at any time, but will be able to exit only if you collected all treasure chests. "Exit" does not mean that you have to get off the grid, just that you are at (M,N) with all the treasures.
What is the minimum time you need to accomplish this task?
Several test cases, each begins with two integers on a line, M and N (2 <= M,N <= 100). M lines follow with N characters, each of them one of N,E,S or W, indicating the side of the cell that is open at time 0.
If we label a cell as (r,c), N,E,S,W allow movement to (r-1,c),(r,c+1),(r+1,c),(r,c-1) respectively.
Next line contains the integer K (1 <= K <= 8), the number of cells containing treasure chests. K lines follow with two integers R and C on each, denoting the coordinates of treasure chests. All K locations will be distinct and none of them will be at (1,1) or (M,N).
The last case is followed by the line containing two zeros.
For each test case print the minimum time needed to exit the maze after collecting all treasure chests, as described in the problem statement.
2 2 EE NN 1 1 2 0 0
2