POJ 1573 Robot Motion(DFS)

POJ 1573 Robot Motion(DFS)

http://poj.org/problem?id=1573

题意:给你一个R*C的棋盘字母矩阵,该矩阵只由N,S,E,W 4个字母构成,分别表示机器人如果走到当前点将往哪个方向走下一步.然后给了你机器人的入口位置(始终在最上一行的某一列做入口),要你输出机器人在该字符矩阵中的行走状况:几步能走出棋盘或者要进入一个几步的死循环.

分析:网上也有用循环判断模拟做这题的,不过我个人感觉DFS做的话应该更简单.

我们用char map[15][15]来表示原始的字符矩阵,然后用dist[r][c]来表示机器人走到(r,c)格子的时候走了几步.用cnt表示机器人当前已经走过了多少步.

然后DFS从起点开始模拟,没经过一个未走过的格子就更新dist,且把cnt++,如果我们此时走到了一个已经走过的格子,说明机器人进入循环了.那么机器人整个路径中:(假设此时的坐标为r,c)

只走过1次的路长为dist[r][c]-1.(想想是不是)

循环中的路长为 cnt-dist[r][c] (想想是不是)

AC代码:

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=15;
int dr[]={-1,1,0,0};
int dc[]={0,0,-1,1};
int dir[255];
char map[maxn][maxn];
int dist[maxn][maxn];
int R,C,col;    //col表示入口的列号
int ans1,ans2;//分别表示进入循环后的两段steps,如果不进入循环则ans1为答案
bool dfs(int cnt,int r,int c)//当前是第cnt步,返回true则不进入死循环,false则进入死循环
{
    int d=dir[map[r][c]];//d是当前格的方向
    if(dist[r][c]==-1)   //该格未走过
    {
        dist[r][c]=cnt;
        int nr=r+dr[d], nc=c+dc[d];
        if(nr<0||nr>=R||nc<0||nc>=C) {ans1=cnt; return true;} //已经走出边界
        return dfs(cnt+1,nr,nc);
    }
    else                 //该格已走过
    {
        ans1= dist[r][c]-1;
        ans2= cnt-dist[r][c];
        return false;
    }
}
int main()
{
    dir['N']=0,dir['S']=1,dir['W']=2,dir['E']=3;
    while(scanf("%d%d%d",&R,&C,&col)==3&&R)
    {
        for(int i=0;i<R;i++) scanf("%s",map[i]);
        memset(dist,-1,sizeof(dist));
        if(dfs(1,0,col-1)) printf("%d step(s) to exit\n",ans1);
        else printf("%d step(s) before a loop of %d step(s)\n",ans1,ans2);
    }
    return 0;
}