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

HDU1035深搜

原文：http://blog.csdn.net/kevin66654/article/details/41124363