HDU1035深搜

HDU1035深搜

/*
	HDU1035
	題意：
	給定一個字符矩陣，N S W E分別代表向上，下，左，右前進 
	模擬搜索，判斷：
	若能走出字符矩陣，則Yes，輸出步數 
	若走不出矩陣，那麼必定有圈存在，必定在矩陣中存在一個點會訪問第二次
*/
 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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;ib;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 
T gcd(T a,T b)
{
    return b==0?a:gcd(b,a%b);  
}

template   
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
*/