poj1573 Robot Motion（DFS）

题目链接

题意

一个机器人在给定的迷宫中行走，在迷宫中的特定位置只能按照特定的方向行走，有两种情况：①机器人按照方向序列走出迷宫，这时输出机器人走出迷宫的步数；②机器人在迷宫中陷入了循环，这种情况要输出机器人陷入循环前所走的步数以及循环的步数。

思路

走迷宫问题一般使用BFS或DFS求解，这里我使用DFS来求解。机器人能顺利走出迷宫的情况比较容易判断，主要是如何判断机器人陷入了循环以及陷入循环后的输出。我使用visit[r][c]来记录位置（r，c）是否被访问过，使用steps[r][c]记录机器人从起点到点（r，c）所经历的步数。假设（r，c）按照指令走了一步后的坐标为（nr，nc），若（nr，nc）已不在迷宫中，则输出结果；若（nr，nc）还在迷宫中，若该位置未被访问过，则按照指令走下一步，若（nr，nc）被访问过，则说明陷入了循环，位置（nr，nc）即是循环的起点，steps[nr][nc]-1即陷入循环前机器人所行走的步数，steps[r][c]-steps[nr][nc]+1即为循环的步数。

代码

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int N = ;

 char ins[N][N];

 int visit[N][N];

 int steps[N][N];

 int m, n, sc;

 void dfs(int r, int c, int stp)

 {

     int nr, nc;

     switch(ins[r][c])

     {

     case 'N':

         nr = r - ;

         nc = c;

         break;

     case 'E':

         nr = r;

         nc = c + ;

         break;

     case 'S':

         nr = r + ;

         nc = c;

         break;

     case 'W':

         nr = r;

         nc = c - ;

         break;

     }

     if(nr>=&&nr<m && nc>=&&nc<n)  //还在迷宫中

     {

         if(!visit[nr][nc])  //(nr, nc)未被访问

         {

             steps[nr][nc] = stp + ;

             visit[nr][nc] = ;

             dfs(nr, nc, stp+);

         }

         else    //出现循环

         {

             printf("%d step(s) before a loop of %d step(s)\n", steps[nr][nc]-, stp-steps[nr][nc]+);

             return;

         }

     }

     else    //走出迷宫

     {

         printf("%d step(s) to exit\n", stp);

         return;

     }

 }

 int main()

 {

     //freopen("poj1573.txt", "r", stdin);

     while(cin>>m>>n>>sc && m)

     {

         memset(visit, , sizeof(visit));

         memset(steps, , sizeof(steps));

         for(int i=; i<m; i++)

             cin>>ins[i];

         sc--;

         visit[][sc] = ;

         steps[][sc] = ;

         dfs(, sc, );

     }

     return ;

 }

巴特西

poj1573 Robot Motion（DFS）

最新文章

热门文章