Problem1068--蠢蠢机器人II

1068: 蠢蠢机器人II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 200  Solved: 77
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI发明了蠢蠢机器人,蠢蠢机器人被编程成只能按照其路径上的指令进行操作。
机器人下一个移动方向的指令有以下四种:
- N(向上走一格)
- S(向下走一格)
- E(向右走一格)
- W(向左走一格)

http://acm.hdu.edu.cn/data/images/1035-1.gif
如上图样例一所示,机器人从正上方走入网格矩阵,经过10步从最左边走出方格。
如样例二所示,机器人从正上方走入方格矩阵,经过三步后,陷入了一个循环,循环的路径长度为8.
现在PIPI希望你写一个程序来判断机器人离开网格矩阵需要多长时间,或者说机器人是如何循环的。
输出格式见样例。



Input

输入包含多组测试用例。
对于每个样例。
第一行包含三个数字 n,m,t ,n代表矩阵的行数,m代表矩阵的列数,t代表机器人从正上方的第t列进入迷宫。(1<=n,m<=10, 1=<t<=m)
接下来输入一个n行m列的网格矩阵。
0 0 0 代表输入结束。

Output

对于输入的每个样例,都有一行输出。

要么机器人遵循一定数量的指令,从任意一边的网格中退出,要么机器人遵循一定数量位置上的指令一次,然后重复某些位置上的指令。

下面的示例输入对应于上面的两个网格,并说明了两种输出形式。

Sample Input

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

Sample Output

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

Source/Category