【poj】1573 Robot Motion 模拟 机器人

#include <stdio.h>
#include <string.h>

char ins[10][10]; //指令数组
int vis[10][10]; //标记已访问坐标
int fa[10][10]; //移到双亲坐标的指令

int main()
{
       int r, c, s, i, x, y, step, tstep, j, lx, ly, tx, ty,
              off[4][2]={0,1, 1,0, 0,-1, -1,0};//四个方向的偏移量
       while(scanf("%d%d%d", &r, &c, &s) && (r || c || s))
       {
              memset(vis, 0, sizeof(vis));
              memset(fa, 0, sizeof(fa));
              for (i=0; i<r; i++)
              {
                     scanf("%s", ins[i]);
              }
              y = --s; //起始column标量和数组column相差1
              x = 0;
              step = 0;
              while(1)
              {
                     if (x >= r || x < 0 || y >= c || y < 0) //数组越界,即robot已经exit
                     {
                            printf("%d step(s) to exitn", step);
                            break;
                     }
                     step++;
                     vis[x][y] = 1;
                     switch(ins[x][y])
                     { //四个ESWN方向分别定义为0123
                            case 'E': j = 0; break;
                            case 'S': j = 1; break;
                            case 'W': j = 2; break;
                            case 'N': j = 3; break;
                     }
                     if (vis[x+off[j][0]][y+off[j][1]]) //如果又走到了访问过的点,则有loop
                     {
                            tstep = step; //记录loop一圈后总共的步数
                            lx = x + off[j][0];
                            ly = y + off[j][1];
                            while(!(x+off[fa[x][y]][0]==lx && y+off[fa[x][y]][1]==ly)) //根据fa数组倒退
                            {
                                   tx = off[fa[x][y]][0];
                                   ty = off[fa[x][y]][1];
                                   x += tx;
                                   y += ty;
                                   step--;
                            }
                            step -= 2; //多记了两个step减去.
                            printf("%d step(s) before a loop of %d step(s)n", step, tstep-step);
                            break;
                     }
                     x += off[j][0];
                     y += off[j][1];
                     fa[x][y] = (j + 2) % 4; //相反方向的回溯
              }
       }
       return 0;
}

2011-04-07 15:33 发表于百度空间，今搬至CU。