• <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>

            infinity

              C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理 ::
              36 隨筆 :: 0 文章 :: 25 評論 :: 0 Trackbacks
            http://acm.pku.edu.cn/JudgeOnline/problem?id=2312
            poj 2312 Battle City
            簡單的BFS





            Source Code

            Problem: 2312 User: lovecanon
            Memory: 1244K Time: 16MS
            Language: GCC Result: Accepted

            #include<stdio.h>
            typedef 
            struct node 
            {
                
            int x;
                
            int y;
            }node;
            node Q[
            100000];
            char board[301][301];
            int step[301][301];
            int m,n;
            const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

            int ok(int x,int y)
            {
                
            if(x>=0&&x<m&&y>=0&&y<n) return 1;
                
            else return 0;
            }

            void solve(int x1,int y1,int x2,int y2)
            {
                
            int i,j,cntx,cnty,nextx,nexty,head,tail,tmp,minstep=0x7fffffff;
                cntx
            =x1;cnty=y1;head=tail=0;
                
            for(i=0;i<m;i++)
                    
            for(j=0;j<n;j++)
                        step[i][j]
            =0x7fffffff;
                step[cntx][cnty]
            =0;

                
            while(1)
                {
                    
            for(i=0;i<4;i++)
                    {
                        nextx
            =cntx+dx[i];
                        nexty
            =cnty+dy[i];
                        
            if(ok(nextx,nexty))
                        {
                            
            if(board[nextx][nexty]=='E')
                            {
                                tmp
            =step[cntx][cnty]+1;
                                
            if(tmp<step[nextx][nexty])
                                {
                                    step[nextx][nexty]
            =tmp;
                                    Q[
            ++tail].x=nextx;
                                    Q[tail].y
            =nexty;
                                }
                            }
                            
            if(board[nextx][nexty]=='B')
                            {
                                tmp
            =step[cntx][cnty]+2;
                                
            if(tmp<step[nextx][nexty])
                                {
                                    step[nextx][nexty]
            =tmp;
                                    Q[
            ++tail].x=nextx;
                                    Q[tail].y
            =nexty;
                                }
                            }
                            
            if(board[nextx][nexty]=='T')
                            {
                                
            if(step[cntx][cnty]+1<minstep)  minstep=step[cntx][cnty]+1;
                            }
                        }
                    }
                    
            if(head==tail)  break;
                    
            else
                    {
                        cntx
            =Q[++head].x;
                        cnty
            =Q[head].y;
                    }
             
                }
                
            if(minstep==0x7fffffff)  printf("-1\n");
                
            else printf("%d\n",minstep);

            }

            int main()
            {
                
            while(1)
                {
                    
            int i,j;
                    
            int x1,y1,x2,y2;

                    scanf(
            "%d%d",&m,&n);
                    getchar();

                    
            if(m==0&&n==0return 0;

                    
            for(i=0;i<m;i++)
                    {
                        
            for(j=0;j<n;j++)
                        {
                            board[i][j]
            =getchar();
                            
            if(board[i][j]=='Y')
                            {
                                x1
            =i;y1=j;
                            }
                            
            if(board[i][j]=='T')
                            {
                                x2
            =i;y2=j;
                            }
                        }
                        getchar();
                    }
                    solve(x1,y1,x2,y2);
                }
                
            return 0;

            }

            posted on 2008-09-20 04:38 infinity 閱讀(560) 評論(1)  編輯 收藏 引用 所屬分類: acm

            評論

            # re: poj 2312 Battle City 2012-09-16 22:31 ty78
            我用X代表列 Y代表行 為什么會錯?
            我都把X,Y相關的替換?能說明下嘛,我是個菜鳥
            #include<stdio.h>
            typedef struct node
            {
            int x;
            int y;
            }node;
            node Q[100000];
            char board[301][301];
            int step[301][301];
            int m,n;
            const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};

            int ok(int x,int y)
            {
            if(x>=0&&x<m&&y>=0&&y<n) return 1;
            else return 0;
            }

            void solve(int x1,int y1,int x2,int y2)
            {
            int i,j,cntx,cnty,nextx,nexty,head,tail,tmp,minstep=0x7fffffff;
            cntx=x1;cnty=y1;head=tail=0;
            for(i=0;i<m;i++)
            for(j=0;j<n;j++)
            step[i][j]=0x7fffffff;
            step[cnty][cntx]=0;

            while(1)
            {
            for(i=0;i<4;i++)
            {
            nextx=cntx+dx[i];
            nexty=cnty+dy[i];
            if(ok(nextx,nexty))
            {
            if(board[nexty][nextx]=='E')
            {
            tmp=step[cnty][cntx]+1;
            if(tmp<step[nexty][nextx])
            {
            step[nexty][nextx]=tmp;
            Q[++tail].x=nextx;
            Q[tail].y=nexty;
            }
            }
            if(board[nexty][nextx]=='B')
            {
            tmp=step[cnty][cntx]+2;
            if(tmp<step[nexty][nextx])
            {
            step[nexty][nextx]=tmp;
            Q[++tail].x=nextx;
            Q[tail].y=nexty;
            }
            }
            if(board[nexty][nextx]=='T')
            {
            if(step[cnty][cntx]+1<minstep) minstep=step[cnty][cntx]+1;
            }
            }
            }
            if(head==tail) break;
            else
            {
            cntx=Q[++head].x;
            cnty=Q[head].y;
            }

            }
            if(minstep==0x7fffffff) printf("-1\n");
            else printf("%d\n",minstep);

            }

            int main()
            {
            while(1)
            {
            int i,j;
            int x1,y1,x2,y2;

            scanf("%d%d",&m,&n);
            getchar();

            if(m==0&&n==0) return 0;

            for(i=0;i<m;i++)
            {
            for(j=0;j<n;j++)
            {
            board[i][j]=getchar();
            if(board[i][j]=='Y')
            {
            x1=j;y1=i;
            }
            if(board[i][j]=='T')
            {
            x2=i;y2=j;
            }
            }
            getchar();
            }
            solve(x1,y1,x2,y2);
            }
            return 0;

            }

              回復  更多評論
              

            99久久成人18免费网站| 狠狠色丁香婷婷综合久久来来去| 97久久超碰国产精品旧版| 日本久久久久久久久久| 国产福利电影一区二区三区久久久久成人精品综合 | 久久AAAA片一区二区| 中文精品久久久久国产网址| 久久91综合国产91久久精品| 亚洲国产另类久久久精品小说 | 四虎影视久久久免费| 久久天天躁狠狠躁夜夜不卡| 性高湖久久久久久久久AAAAA| 亚洲国产成人久久精品99 | 2021精品国产综合久久| 国产精品对白刺激久久久| 久久99热精品| 久久久WWW成人免费毛片| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 亚洲精品视频久久久| 久久激情五月丁香伊人| 热RE99久久精品国产66热| 国内精品久久久久影院薰衣草| 国内精品久久久久影院日本| 国产精品久久久99| 久久精品视频91| 亚洲va中文字幕无码久久不卡| 精品国产综合区久久久久久| 久久亚洲欧洲国产综合| 久久中文字幕精品| 精品亚洲综合久久中文字幕| 人人狠狠综合88综合久久| 久久99国产精品尤物| 久久久久人妻一区精品| 91精品国产高清久久久久久io | 久久精品无码一区二区日韩AV| 久久久久久精品免费看SSS| 999久久久国产精品| 久久无码国产专区精品| 久久久久久国产a免费观看不卡| av国内精品久久久久影院| 理论片午午伦夜理片久久 |