POJ 1573&hdu 1035 Robot Motion【簡易シミュレーション】

テーマリンク:http://poj.org/problem?id=1573
                   http://acm.hdu.edu.cn/showproblem.php?pid=1035
Robot Motion
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：3893    Acceepted Submission(s)：1817
Problem Description

A robot has been programmed to follow the instructions in its path.Instructions for the next direction the robot is to move are laid down a grid.The possible instructions ares are 
N north(up the page)
S south(down the page)
E east(to the right on the page)
W west(to the left on the page)
For example、suppose the robot starts on the north(top)side of Grid 1 and starts south(down).The path the robot follows is shown.The robot goes through 10 instructions the gride beree aving.the.id
Compre what happens in Grid 2:the robot goes through 3 instructions only once，and then starts a loop through 8 instructions，and never exits.
You are to write a program that determins hoow long it Taes a robot to get out of the grid or how the robot loops around.
 
Input
The e e will be one or more grids for robots to navigate.The data for each is in the following form.On the first line are three inters separated by blanks:the number of rows in the grid，the number of colds。and the number of the column n in which the robot enters from the north.The possible entrycolumnsarare numbed starting with th the left.The n come the rows of the directctinstrectctions.Each.Each grgridels s s s s s s strererererererererererereres.Ecommmmmmininininininininininininininininininininininininsts.Epas.Ecolushshshshshshshshshshshshshs.Each sts.Epas s.Each ers N，S，E，or W withのblanks.The end of input is indicated by a row containing 0.
 
Output
For each gride in the input the is one line of output.Either the robost follows a certain number of instructions and exits the grid on on on the four sides or else the roboot follows the the instruct the Cartionsand the n the instructions on some number of locations repeatdely.The sample input below coreress ponds to the two grids above and illustration the tword.The word"step"is alys mdiatelthe"
 
Sample Input

   
   
   
   

    
    
    
    3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    10 step(s) to exit
3 step(s) before a loop of 8 step(s)
   
   
   
   

 
ソurce
Mid-Central USA 1999
 
kb神の紹介に感謝します。

//AC 168kb 0ms POJ1573 C++ 
//AC  256kb 0ms hdu 1035 C++
#include<stdio.h>
#include<string.h>

char map[15][15];
int dis[15][15];

int main()
{
	int n,m,s;
	int i,j;
	int si,sj;
	int step;
	int step1;
	while(scanf("%d%d%d%*c",&n,&m,&s)!=EOF && m)
	{
		step=0;step1=0;
		memset(dis,0,sizeof(dis));
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
				scanf("%c",&map[i][j]);
			getchar();
		}
		si=1;sj=s;
		while(si>=1 && si<=n && sj>=1 && sj<=m &&!dis[si][sj])
		{
			step++;
			dis[si][sj]=1;
			if(map[si][sj]=='W')
				sj-=1;
			else if(map[si][sj]=='E')
				sj+=1;
			else if(map[si][sj]=='S')
				si+=1;
			else if(map[si][sj]=='N')
				si-=1;
		} 
		if(!(si>=1 && si<=n) || !(sj>=1 && sj<=m))
			printf("%d step(s) to exit
",step);
		else
		{
			memset(dis,0,sizeof(dis));
			while(!dis[si][sj])
			{
				step1++;
				dis[si][sj]=1;
				if(map[si][sj]=='W')
					sj-=1;
				else if(map[si][sj]=='E')
					sj+=1;
				else if(map[si][sj]=='S')
					si+=1;
				else if(map[si][sj]=='N')
				si-=1;
			}
			step=step-step1;
			printf("%d step(s) before a loop of %d step(s)
",step,step1);
		}		
	}
	return 0;
}