The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

湘潭市程序设计比赛 I robot,bfs

这题出得不错，在传统的bfs上加了点改进，好题~
#include<iostream>
#include<cmath>
using namespace std;
int const maxn=110;
int mm[maxn][maxn];
int v[maxn][maxn][4];//0上，1右，2下，3左
struct node
{

    int step;
    int x,y;
    int dir;
}q[10000000];

int n,m;
int t;


int sx,sy;
int tx,ty;
void input()
{
    scanf("%d%d",&n,&m);
    char s[200];
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%s",s);
        int len=strlen(s);
        for(int j=0;j<len;j++)
        {

            if(s[j]=='#')mm[i][j]=-1;
            else if(s[j]=='.')mm[i][j]=0;
            else if(s[j]=='S'){sx=i;sy=j;mm[i][j]=0;}
            else if(s[j]=='T'){tx=i;ty=j;mm[i][j]=0;}
        }
    }
}

bool god(int x,int y)
{

    if(x>=0&&x<n&&y>=0&&y<m&&mm[x][y]!=-1)
        return true;
    else
        return false;
}

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

int main()
{

    int l,r;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        memset(v,0,sizeof(v));
        input();
        //
        l=r=1;
        q[l].step=0;
        q[l].dir=0;
        q[l].x=sx;
        q[l].y=sy;
        v[sx][sy][0]=1;
        //初始化
        while(l<=r)
        {
            if(q[l].x==tx&&q[l].y==ty)
                break;
            for(i=0;i<4;i++)
            {
                if(i==q[l].dir)
                {

                    int nx=q[l].x+dir[i][0];
                    int ny=q[l].y+dir[i][1];
                    if(god(nx,ny)&&v[nx][ny][i]==0)
                    {

                        v[nx][ny][i]=1;
                        r++;
                        q[r].x=nx;
                        q[r].y=ny;
                        q[r].step=q[l].step+1;
                        q[r].dir=q[l].dir;
                    }
                }
                else
                {
                    int nr=(q[l].dir+1)%4;
                    int nl=(((q[l].dir-1)%4+4)%4);
                    if(v[q[l].x][q[l].y][nr]==0)
                    {
                        v[q[l].x][q[l].y][nr]=1;
                        r++;
                        q[r].x=q[l].x;
                        q[r].y=q[l].y;
                        q[r].step=q[l].step+1;
                        q[r].dir=nr;
                    }
                    if(v[q[l].x][q[l].y][nl]==0)
                    {
                        v[q[l].x][q[l].y][nl]=1;
                        r++;
                        q[r].x=q[l].x;
                        q[r].y=q[l].y;
                        q[r].step=q[l].step+1;
                        q[r].dir=nl;
                    }
                }
            }
            l++;


        }
        if(l<=r)
            printf("%d\n",q[l].step);
        else
            printf("-1\n");
    }
    return 0;

}

posted on 2010-05-22 22:05 abilitytao 阅读(1606) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理