Robot Motion
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3466 Accepted Submission(s): 1608
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 in a grid. The possible instructions 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 in the grid before leaving the grid.
Compare 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 determines how long it takes a robot to get out of the grid or how the robot loops around.
#include<stdio.h> #include<string.h> #include<string.h> const int MAXN=1000; char map[MAXN][MAXN]; int t[MAXN][MAXN]; int main() { int n,m,k; int x,y; while(scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; scanf("%d",&k); for(int i=0;i<n;i++) scanf("%s",&map[i]); x=0; y=k-1; memset(t,0,sizeof(t)); t[x][y]=1; while(1) { if(map[x][y]=='W') { y--; if(y<0) { printf("%d step(s) to exit\n",t[x][y+1]); break; } if(t[x][y]!=0) { printf("%d step(s) before a loop of %d step(s)\n",t[x][y]-1,t[x][y+1]-t[x][y]+1); break; } t[x][y]=t[x][y+1]+1; } else if(map[x][y]=='E') { y++; if(y>=m) { printf("%d step(s) to exit\n",t[x][y-1]); break; } if(t[x][y]!=0) { printf("%d step(s) before a loop of %d step(s)\n",t[x][y]-1,t[x][y-1]-t[x][y]+1); break; } t[x][y]=t[x][y-1]+1; } else if(map[x][y]=='N') { x--; if(x<0) { printf("%d step(s) to exit\n",t[x+1][y]); break; } if(t[x][y]!=0) { printf("%d step(s) before a loop of %d step(s)\n",t[x][y]-1,t[x+1][y]-t[x][y]+1); break; } t[x][y]=t[x+1][y]+1; } else { x++; if(x>=n) { printf("%d step(s) to exit\n",t[x-1][y]); break; } if(t[x][y]!=0) { printf("%d step(s) before a loop of %d step(s)\n",t[x][y]-1,t[x-1][y]-t[x][y]+1); break; } t[x][y]=t[x-1][y]+1; } } } return 0; }