• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            


            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 閱讀(1613) 評論(0)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    




            






            

				

            


    
    







            
	   
	



亚洲欧美成人久久综合中文网|
久久久久国产精品三级网|
久久精品国产亚洲AV不卡|
狠狠色综合网站久久久久久久高清
|
久久精品人人槡人妻人人玩AV|
久久香蕉超碰97国产精品|
国产精品久久久久久一区二区三区
|
久久成人影院精品777|
久久综合九色欧美综合狠狠
|
久久久久久久波多野结衣高潮|
国产精品一区二区久久不卡|
久久久精品久久久久久|
久久66热人妻偷产精品9|
久久久久亚洲AV成人网人人网站|
伊人久久大香线蕉综合Av|
久久成人国产精品一区二区|
99精品国产在热久久无毒不卡|
麻豆久久|
国产精品VIDEOSSEX久久发布|
亚洲va久久久噜噜噜久久|
久久久久久噜噜精品免费直播|
日韩精品久久久久久久电影蜜臀|
青春久久|
伊人久久无码精品中文字幕|
99久久免费国产精品|
999久久久免费精品国产|
狠狠色噜噜色狠狠狠综合久久|
久久av免费天堂小草播放|
91精品国产91久久综合|
亚洲色婷婷综合久久|
亚洲狠狠婷婷综合久久蜜芽|
色婷婷综合久久久久中文字幕
|
亚洲欧洲久久av|
热久久最新网站获取|
婷婷久久综合九色综合绿巨人|
久久久久无码精品国产app|
国产精品欧美久久久久无广告|
色综合色天天久久婷婷基地|
久久精品国产精品青草app|
99久久免费国产精精品|
久久99精品国产麻豆宅宅|