Problem F : Maze Traversal

A common problem in artificial intelligence is negotiation of a maze. A maze has corridors and walls. The robot can proceed along corridors, but cannot go through walls.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

For this problem, you will input the dimensions of a maze, as two integer values on the first line. Of the two numbers, the first is the number of rows and the second is the number of columns. Neither the number of rows nor columns will exceed 60.

Following these numbers will be a number of rows, as specified previously. In each row there will be a character for each column, with the row terminated by the end of line. Blank spaces are corridors, asterisks are walls. There needn't be any exits from the maze.

Following the maze, will be an initial row and column specified as two integers on one line. This gives the initial position of the robot. Initially the robot will be facing North (toward the first row).

The remaining input will consist of commands to the robot, with any amount of interspersed white-space. The valid commands are:

R

rotate the robot 90 degrees clockwise (to the right)

L

rotate the robot 90 degrees counter-clockwise (to the left)

F

move the robot forward, unless a wall prevents this, in which case do nothing

Q

quit the program, printing out the current robot row, column and orientation

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

The final row and column must be integers separated by a space. The orientation must be one of N,W,S,E and separated from the column by a space.

Sample Input

1

7 8
********
* * * **
* *    *
* * ** *
* * *  *
*   * **
********
2 4
RRFLFF FFR
FF
RFFQ

Sample Output

5 6 W

---

University of Porto ACM Programming Contest / Round 1 / 2002/05/22

#include <stdio.h>
#include <string.h>
using namespace std;

int main() {
    int n, m, i, j, testcase;
    char g[105][105], cmd[50005];
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        while(getchar() != '\n');
        for(i = 0; i < n; i++)
            gets(g[i]);
        int dx[4] = {-1,1,0,0};//NSWE
        int dy[4] = {0,0,-1,1};
        int dir = 0, x, y, tx, ty;
        dir = 0;
        scanf("%d %d", &x, &y);
        x--, y--;
        while(scanf("%s", cmd) == 1) {
            int ch;
            for(i = 0; cmd[i]; i++) {
                ch = cmd[i];
                if(ch == 'R') {
                    if(dir == 0)        dir = 3;
                    else if(dir == 1)   dir = 2;
                    else if(dir == 2)   dir = 0;
                    else                dir = 1;
                    continue;
                }
                if(ch == 'L') {
                    if(dir == 0)        dir = 2;
                    else if(dir == 1)   dir = 3;
                    else if(dir == 2)   dir = 1;
                    else                dir = 0;
                    continue;
                }
                if(ch == 'Q')   break;
                tx = x+dx[dir], ty = y+dy[dir];
                if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                    continue;
                if(g[tx][ty] == '*')
                    continue;
                x = tx, y = ty;
            }
            if(ch == 'Q')
                break;
        }
        printf("%d %d ", x+1, y+1);
        if(dir == 0)    putchar('N');
        if(dir == 1)    putchar('S');
        if(dir == 2)    putchar('W');
        if(dir == 3)    putchar('E');
        puts("");
        if(testcase)    puts("");
    }
    return 0;
}