首页 > 代码库 > POJ 1573 Robot Motion

POJ 1573 Robot Motion

题意:给你一个棋盘,上面的字母代表机器人要走的方向。如果机器人能走出这个棋盘,则输出机器人所走的步数,否则输出该机器人在走向无限循环前所走的步数,及无限循环所要走的格子数

思路:直接模拟,没有思路(大神可以多考虑些思路)

AC代码:

#include<stdio.h>
#include<string.h>
char str[12][12];
int flag[12][12];
int r,c,s,sum,loop;
void  dfs(int x,int y)
{
    if(x>=r||y>=c||x<0||y<0){
        printf("%d step(s) to exit\n",sum);
        return ;
    }
    if(flag[x][y]==2)
    {
        printf("%d step(s) before a loop of %d step(s)\n",sum-loop,loop);
        return ;
    }
    if(str[x][y]=='E')
    {
        if(flag[x][y]==1)
            loop++;
        else
            sum+=1;
        flag[x][y]+=1;
        dfs(x,y+1);
    }
     else if(str[x][y]=='W')
    {
        if(flag[x][y]==1)
            loop++;
        else
            sum+=1;
        flag[x][y]+=1;
        dfs(x,y-1);
    }
    else if(str[x][y]=='S')
    {
        if(flag[x][y]==1)
            loop++;
        else
            sum+=1;
        flag[x][y]+=1;
        dfs(x+1,y);
    }
    else
    {
        if(flag[x][y]==1)
            loop++;
        else
            sum+=1;
        flag[x][y]+=1;
        dfs(x-1,y);
    }
}
int main()
{
    while(scanf("%d %d %d",&r,&c,&s)!=EOF)
    {
        if(r==0&&c==0&&s==0)break;
        sum=0;
        loop=0;
        int i,j;
        memset(str,0,sizeof(str));
        memset(flag,0,sizeof(flag));
        for(i=0;i<r;i++){
            getchar();
            scanf("%s",str[i]);
        }

        dfs(0,s-1);
    }
    return 0;
}