HDU1035深度搜索

/*

	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

*/