poj1573(Robot Motion)

主要是思维，dis[s][t]数组的作用

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int map[101][101];
int v[101][101],dis[101][101];
int n,m,x;
int jx[]= {-1,1,0,0};
int jy[]= {0,0,-1,1};
void bfs(int s,int t)
{
    int sum=0;
    memset(v,0,sizeof(v));
    memset(dis,0,sizeof(dis));
    while(!v[s][t]&&s>=0&&s<n&&t>=0&&t<m)
    {
        v[s][t]=1;
        dis[s][t]=sum;
        int xx=s+jx[map[s][t]];
        int yy=t+jy[map[s][t]];
        s=xx;
        t=yy;
        sum++;
    }
    if(s>=0&&s<n&&t>=0&&t<m)
        printf("%d step(s) before a loop of %d step(s)
",dis[s][t],sum-dis[s][t]);
    else printf("%d step(s) to exit
",sum);
}
int main()
{
    char a[101][101];
    while(scanf("%d%d%d",&n,&m,&x)!=EOF)
    {
        if(n==0&&m==0&&x==0) break;
        for(int i=0; i<n; i++)
        {
            scanf("%s%*c",a[i]);
        }
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(a[i][j]=='N')
                    map[i][j]=0;
                else if(a[i][j]=='S')
                    map[i][j]=1;
                else if(a[i][j]=='E')
                    map[i][j]=3;
                else if(a[i][j]=='W')
                    map[i][j]=2;
            }
        }
        bfs(0,x-1);
    }
    return 0;
}