HDU ACM 1035 Robot Motion 简略模拟题

HDU ACM 1035 Robot Motion 简单模拟题

分析：一步步的走，走出矩阵则说明没有环，若走到已经走过的地方，说明有环，按格式输出结果,OK.

#include<iostream>
using namespace std;

#define N 15
int dir[4][2]={-1,0,1,0,0,-1,0,1};
char map[N][N];
int vis[N][N];
char ch[]="NSWE";
int n,m;

int id(char c)
{
	int i;

	for(i=0;i<4;i++)
		if(ch[i]==c) return i;
}

void sovle(int s)
{
	int i,j,k;

	i=k=1;
	j=s;
	memset(vis,0,sizeof(vis));
	vis[i][j]=k;
	while(true)
	{
		s=i;
		i+=dir[id(map[i][j])][0];
		j+=dir[id(map[s][j])][1];
		if(i<1 || i>n || j<1 ||j>m)
		{
			printf("%d step(s) to exit\n",k);
			break;
		}
		if(vis[i][j])
		{
			printf("%d step(s) before a loop of %d step(s)\n",vis[i][j]-1,k-vis[i][j]+1);
			break;
		}
		vis[i][j]=++k;
	}
}

int main()
{
	int s,i,j;

	while(cin>>n>>m,n||m)
	{
		cin>>s;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
				cin>>map[i][j];
			getchar();
		}
		sovle(s);
	}
    return 0;      
}