1573.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

//#define debug 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

#define INF 30000
#define NMAX 52
char a[NMAX][NMAX];
int m[NMAX][NMAX];
int M,N,stx,sty;
int xp[4]={0,1,0,-1};
int yp[4]={-1,0,1,0};
int getdir(char a)
{
	switch(a)
	{
	case 'N':return 0;break;
	case 'E':return 1;break;
	case 'S':return 2;break;
	case 'W':return 3;break;
	}
}

void solve()
{
	int dir;
	int flag=0;
	int before=0;
	int loop=0;
	memset(m,0,sizeof(m));
	sty=1;
	int	step=1;
	m[sty][stx]=1;
	while(1)
	{
		dir=getdir(a[sty][stx]);
		sty+=yp[dir];
		stx+=xp[dir];
		if(sty<1||stx<1||sty>M||stx>N)
		{
			flag=1;
			break;
		}
		if(m[sty][stx])
		{
			before=m[sty][stx]-1;
			loop=step-m[sty][stx]+1;
			flag=0;
			break;
		}
		step++;
		m[sty][stx]=step;
	}
	if(flag)
		printf("%d step(s) to exit\n",step);
	else
		printf("%d step(s) before a loop of %d step(s)\n",before,loop);



}

int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	int i,j;
	memset(a,0,sizeof(a));
	while(1)
	{
		scanf("%d%d%d",&M,&N,&stx);
		if(!M)
			break;
		for(i=1;i<=M;i++)
		{
			a[i][0]='0';
			scanf("%s",a[i]+1);
		}
		solve();
	}
	
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}