Robot Motion

骑猪看日落 2022-05-26 06:57 168阅读 0赞

链接：http://poj.org/problem?id=1573

Problem Description：

机器人已经被编程以遵循其路径中的指示。机器人要移动的下一个方向的说明放在网格中。可能的指令是  
N北（页面上）  
S南（页面下）  
E东（页面右）  
W西（页面左）  
例如，假设机器人在北面开始（顶部）网格1的一侧并开始向南（向下）。显示了机器人遵循的路径。离开电网之前，机器人会通过电网中的10条指令。  
比较Grid 2中发生的事情：机器人只经历3次指令，然后通过8条指令开始循环，并且永远不会退出。  
你要编写一个程序来确定一个机器人离开电网需要多长时间，或者机器人如何循环。

Input：

将有一个或多个机器人导航网格。每个数据的格式如下。第一行是由空格分隔的三个整数：网格中的行数，网格中的列数以及机器人从北方进入的列数。可能的输入栏从左边的一个开始编号。然后来到方向指示的行。每个网格至少有一行和最多10行和指令列。指令行只包含字符N，S，E或W，没有空格。输入的结尾由包含0 0 0的行表示。

Output：

对于输入中的每个网格，都有一行输出。机器人遵循一定数量的指令并从四边中的任何一边离开网格，或者机器人遵循一定数量的位置上的指令，然后重复若干位置上的指令。下面的示例输入对应于上面的两个网格，并说明了两种形式的输出。无论前面的数字是否为1，“step”一词总是紧跟“（s）”。

Sample Input：

3 6 5  
NEESWE  
WWWESS  
SNWWWW  
4 5 1  
SESWE  
EESNW  
NWEEN  
EWSEN

0 0 0

Sample Output：

10 step(s) to exit

3 step(s) before a loop of 8 step(s)

思路：这道题其实也不难，主要是你的思路一定要清晰，明确。我就是卡在了一个细节上。我定义了一个结构体，结构体中每一个成员都有两个变量，一个是字符a，还有一个是用来标记步数的flag，方便后来判断机器人是否陷入循环。flag的初值都定义为0，后来走一步就更新一个flag。

My DaiMa：

#include<stdio.h>
    #include<iostream>
    using namespace std;
    typedef struct
    {
        
        char a;
        int flag;
    }character;
    character s[101][101];
    int main()
    {
        
        int n,m,t,k,x;
        char ch[101];
        while(~scanf("%d%d",&n,&m))
        {
        
            if(n==0||m==0)
                break;
            else
            {
        
                scanf("%d",&t);
                for(int i=0;i<n;i++)
                {
        
                    scanf("%s",ch);
                    for(int j=0;j<m;j++)
                    {
        
                        s[i][j].a=ch[j];
                        s[i][j].flag=0;//初定义
                    }
                }
                int i,j;
                i=0,j=t-1,k=x=0;//k是标记机器人的步数，x是标记机器人是否进入了循环
                while((i>=0&&i<n)&&(j>=0&&j<m))
                {
        
                    k++;//只要机器人还没有离开网格，就得走下一步，即k++
                    if(s[i][j].flag!=0)//如果它的flag不等于0的话，就说明机器人陷入循环
                    {
        
                        x=-1;
                        break;
                    }
                    s[i][j].flag=k;//让flag记录的是第几步，这样的话，
                    if(s[i][j].a=='W')//当循环时就知道是第几步开始进入了循环
                    {
        
                        j--;
                    }
                    else if(s[i][j].a=='N')
                    {
        
                        i--;
                    }
                    else if(s[i][j].a=='E')
                    {
        
                        j++;
                    }
                    else if(s[i][j].a=='S')
                    {
        
                        i++;
                    }
                }
                if(x==-1)
                    printf("%d step(s) before a loop of %d step(s)\n",s[i][j].flag-1,k-s[i][j].flag);
                else
                    printf("%d step(s) to exit\n",k);
            }
        }
        return 0;
    }<stdio.h>
    #include<iostream>
    using namespace std;
    typedef struct
    {
       
        char a;
        int flag;
    }character;
    character s[101][101];
    int main()
    {
       
        int n,m,t,k,x;
        char ch[101];
        while(~scanf("%d%d",&n,&m))
        {
       
            if(n==0||m==0)
                break;
            else
            {
       
                scanf("%d",&t);
                for(int i=0;i<n;i++)
                {
       
                    scanf("%s",ch);
                    for(int j=0;j<m;j++)
                    {
       
                        s[i][j].a=ch[j];
                        s[i][j].flag=0;//初定义
                    }
                }
                int i,j;
                i=0,j=t-1,k=x=0;//k是标记机器人的步数，x是标记机器人是否进入了循环
                while((i>=0&&i<n)&&(j>=0&&j<m))
                {
       
                    k++;//只要机器人还没有离开网格，就得走下一步，即k++
                    if(s[i][j].flag!=0)//如果它的flag不等于0的话，就说明机器人陷入循环
                    {
       
                        x=-1;
                        break;
                    }
                    s[i][j].flag=k;//让flag记录的是第几步，这样的话，
                    if(s[i][j].a=='W')//当循环时就知道是第几步开始进入了循环
                    {
       
                        j--;
                    }
                    else if(s[i][j].a=='N')
                    {
       
                        i--;
                    }
                    else if(s[i][j].a=='E')
                    {
       
                        j++;
                    }
                    else if(s[i][j].a=='S')
                    {
       
                        i++;
                    }
                }
                if(x==-1)
                    printf("%d step(s) before a loop of %d step(s)\n",s[i][j].flag-1,k-s[i][j].flag);
                else
                    printf("%d step(s) to exit\n",k);
            }
        }
        return 0;
    }