/*
HDU1035
意甲冠军:
给定一个字符矩阵,N S W E分别代表向上,下,剩下,进
模拟搜索,推断:
若能走出字符矩阵。则Yes,输出步数
若走不出矩阵,那么必然有圈存在,必然在矩阵中存在一个点会訪问第二次
*/ #include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
using namespace std; #define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Sca_d(x) scanf("%d",&x)
#define Sca_s(x) scanf("%s",x)
#define Sca_c(x) scanf("%c",&x)
#define Sca_f(x) scanf("%f",&x)
#define Sca_lf(x) scanf("%lf",&x)
#define Fill(x,a) memset(x,a,sizeof(x))
#define MAXN 1110
#define MAXM 1110
#define MAXINT 111111 template <typename T>
T gcd(T a,T b)
{
return b==0?a:gcd(b,a%b);
} template <typename T>
T lcm(T a,T b)
{
return a/gcd(a,b)*b;
} char dir_ch[5]={' ','W','S','E','N'};
int dir_x[5]={0,0,1,0,-1};
int dir_y[5]={0,-1,0,1,0};
//三个常量数组模拟上下左右的字母行动 char map[MAXN][MAXM];
int dist[MAXN][MAXM];
char ch[MAXM];
int m,n,enter; void dfs(int x,int y)
{
int newx,newy,k;
For2(k,1,4)
if (map[x][y]==dir_ch[k])//等于哪个方向。就往那个方向走
{
newx=x+dir_x[k];
newy=y+dir_y[k];
if (newx<1||newx>n||newy>m||newy<1)//假设跑出了地图之外,则已经出了矩阵
{
printf("%d step(s) to exit\n",dist[x][y]);
return;
}
if (!dist[newx][newy])
{
dist[newx][newy]=dist[x][y]+1;//没到目标继续搜索
dfs(newx,newy);
}
else
{
printf("%d step(s) before a loop of %d step(s)\n",
dist[newx][newy]-1,dist[x][y]+1-dist[newx][newy]);
//假设当前产生的子节点之前已经訪问过
//那么。必然在原图之中产生了环。 //当中,环的长度为 dist[x][y]+1-dist[newx][newy]
//从 dist[newx][newy]-1 步后開始出现环
return;
}
}
return;
} int main()
{
//input;
int i,j,k;
while(cin>>n>>m>>enter)
{
if (!n&&!m) break;
Fill(dist,0);
For2(i,1,n)
{
Sca_s(ch);
For2(j,1,m)
map[i][j]=ch[j-1];
}
dist[1][enter]=1;
dfs(1,enter);
}
return 0;
}
/*
附:在问题的例子Input
3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0
*/
05-01 02:29