1035--Robot Motion

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1035

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)

解题思路

/*
- 这个题目最开始一看还是蛮简单的，一道简单的 - 搜题，但是这道题跟以往的迷宫有点差别，就是 - 个题目指定了行走的路径，相对来说也就简单了 - 多，题目有俩种情况： - 1.能出去，输出步数。（出去就代表越 - (⊙_⊙)） - 2.出不去。也就是陷入了循环。也蛮简单，定义 - 个标记数组，走过标记一下，当下次再次走到， - 然走不通。输出即可， - 这里我遇到了一个问题，就是怎么计算环的大小。 - 最开始我的想法是，走到那个循环坐标点，然后再用 - 一个dfs，起点就是最开始点，终点就是此坐 - 点，遍历出步数，然后总步数一减即可，觉得挺 - 单，但是总是输出的是随机数， - 于是就去看了一下大佬们的log，发现了一个好方法， - 可以将之前的走过的坐标记录下来，然后循环遍 - 一遍，找到步数即可。 
*/

代码

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100;
char ma[maxn][maxn];
int vis[maxn][maxn];
int m,n,k;

struct Coordinate
{
    int x,y;
}path[maxn];
void dfs(int x, int y, int cnt)
{
    if(x<0 || x>=m || y<0 || y>=n)
    {
        //found the exit
        cout << cnt << " step(s) to exit" <<endl;
        return;
    }
    if(vis[x][y]) //循环点
    {
        int i;
        for(i=0; i<cnt; ++i)
        {
            if(path[i].x==x && path[i].y==y)
                break;
        }
        cout << i << " step(s) before a loop of " << cnt-i << " step(s)" <<endl;
        return;
    }
    //标记走过
    vis[x][y] = 1;
    //记录坐标
    path[cnt].x = x;
    path[cnt].y = y; 
    if(ma[x][y] == 'N')
    {
        dfs(x-1,y,cnt+1);
    }
    if(ma[x][y] == 'S')
    {
        dfs(x+1,y,cnt+1);
    }
    if(ma[x][y] == 'W')
    {
        dfs(x,y-1,cnt+1);
    }
    if(ma[x][y] == 'E')
    {
        dfs(x,y+1,cnt+1);
    }

}
int main()
{
    while(cin>>m>>n>>k)
    {
        if(!m && !n && !k)
            break;
        memset(vis,0,sizeof(vis));
        for(int i=0; i<m; ++i)
            cin >> ma[i];
        dfs(0,k-1,0); //起点坐标，步数
    }
    return 0;
}