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 阅读(1558) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理