Robot Motion-蒲公英云

Robot Motion

链接：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;
}