Robot Motion

Interview

Time limit1sMemory limit128 MB

Summary

Simulate a robot walking a grid of N/S/E/W arrows from a given top column, and report either the steps to exit or the steps before a loop plus its length.

Level: Medium4 of 10
Topics: Simulation, Graph, Implementation
Solved: No attempts yet

Problem

A robot follows movement instructions laid out on a grid. Each cell of the grid holds a single instruction telling the robot which direction to move next.

N — north (up)
S — south (down)
E — east (right)
W — west (left)

The robot enters the grid from the north (top) edge at a given column. It immediately reads the instruction in the cell it lands on and moves one step in that direction, then follows the instruction in the new cell, and so on.

Eventually exactly one of two things must happen:

The robot walks off one of the four edges of the grid (it exits).
The robot revisits a cell it has already been to, meaning it has entered an endless loop.

For each grid, write a program that reports how many steps the robot takes to leave the grid, or how many steps it takes before entering a loop together with the number of steps in that loop.

Input

The input consists of one or more grids. Each grid is given in the following form.

The first line contains three integers separated by spaces: the number of rows $R$ , the number of columns $C$ , and the column at which the robot enters from the north. Columns are numbered from 1, starting at the left.

The next $R$ lines describe the rows of the grid. Each line contains exactly $C$ characters, each of which is N, S, E, or W, with no spaces.

Every grid satisfies $1 \le R, C \le 10$ . The input ends with a line containing 0 0 0, which must not be processed.

Output

Print exactly one line for each grid.

If the robot exits the grid, print:

X step(s) to exit

where X is the number of instructions the robot follows before walking off an edge.
If the robot enters a loop, print:

Y step(s) before a loop of Z step(s)

where Y is the number of instructions followed before the loop begins and Z is the number of instructions in the loop.

The word step is always immediately followed by (s), whether or not the preceding number is 1.

Examples3

Example 1

Input

3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0

Expected output

10 step(s) to exit
3 step(s) before a loop of 8 step(s)

Example 2
Input
```
1 1 1
N
0 0 0
```
Expected output
```
1 step(s) to exit
```
Example 3
Input
```
1 3 3
WWW
0 0 0
```
Expected output
```
3 step(s) to exit
```