题目链接
http://poj.org/problem?id=1573
题意
一个机器人在给定的迷宫中行走，在迷宫中的特定位置只能按照特定的方向行走，有两种情况：①机器人按照方向序列走出迷宫，这时输出机器人走出迷宫的步数；②机器人在迷宫中陷入了循环，这种情况要输出机器人陷入循环前所走的步数以及循环的步数。
思路
走迷宫问题一般使用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 ;
}