• <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>
            心如止水
            Je n'ai pas le temps
            posts - 400,comments - 130,trackbacks - 0
            題目大意:在N×M的方格上有些地方不可到達,有些地方有警衛,打敗警衛需要額外1個單位的時間。給出起點和終點,求出最少需要多少時間。
            由于每一步消耗的時間可能不一樣,不能夠直接BFS,因此采用SPFA。
            以下是我的代碼:
            #include<queue>
            #include
            <cstdio>
            #include
            <cstring>
            using namespace std;
            const int kMaxn(207);
            const int kInf(0x7f7f7f7f);
            const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

            struct Point
            {
                Point(
            int valuex,int valuey):x(valuex),y(valuey) {}
                
            int x,y;
            };

            int n,m,x,y,endx,endy,d[kMaxn][kMaxn];
            char g[kMaxn][kMaxn];
            bool inq[kMaxn][kMaxn];

            int main()
            {
                
            /*
                freopen("data.in","r",stdin);
                freopen("data.out","w",stdout);
                //
            */

                
            while(scanf("%d%d",&n,&m)==2)
                {
                    
            for(int i=1;i<=n;i++)
                    {
                        getchar();
                        
            for(int j=1;j<=m;j++)
                        {
                            scanf(
            "%c",&g[i][j]);
                            
            if(g[i][j]=='r')
                            {
                                x
            =i;
                                y
            =j;
                            }
                            
            else if(g[i][j]=='a')
                            {
                                endx
            =i;
                                endy
            =j;
                            }
                        }
                    }

                    queue
            <Point> q;
                    memset(inq,
            false,kMaxn*kMaxn*sizeof(bool));
                    
            for(int i=1;i<=n;i++)
                        
            for(int j=1;j<=m;j++)
                            d[i][j]
            =kInf;
                    d[x][y]
            =0;
                    q.push(Point(x,y));
                    inq[x][y]
            =true;
                    
            while(!q.empty())
                    {
                        Point now
            =q.front();
                        q.pop();
                        inq[now.x][now.y]
            =false;

                        
            for(int i=0;i<4;i++)
                        {
                            
            int newx(now.x+dx[i]),newy(now.y+dy[i]);
                            
            if(newx<1 || newx>|| newy<1 || newy>|| g[newx][newy]=='#')
                                
            continue;
                            
            int w(g[newx][newy]=='x'?2:1);
                            
            if(d[newx][newy]>d[now.x][now.y]+w)
                            {
                                d[newx][newy]
            =d[now.x][now.y]+w;
                                
            if(!inq[newx][newy])
                                {
                                    q.push(Point(newx,newy));
                                    inq[newx][newy]
            =true;
                                }
                            }
                        }
                    }

                    
            if(d[endx][endy]<kInf)
                        printf(
            "%d\n",d[endx][endy]);
                    
            else
                        printf(
            "Poor ANGEL has to stay in the prison all his life.\n");
                }

                
            return 0;
            }
            posted on 2011-05-26 16:09 lee1r 閱讀(276) 評論(0)  編輯 收藏 引用 所屬分類: 題目分類:圖論
            亚洲精品无码专区久久同性男| 久久国产乱子伦精品免费午夜| 狠狠综合久久综合中文88| 久久国产精品久久| 亚洲乱亚洲乱淫久久| 伊人久久大香线蕉无码麻豆| 久久精品极品盛宴观看| 久久久久久人妻无码| 国产精品久久久久久搜索| 久久亚洲精品视频| 国産精品久久久久久久| 中文字幕无码久久人妻| 国产精品免费久久| 91久久婷婷国产综合精品青草| 亚洲国产日韩欧美久久| 97久久天天综合色天天综合色hd| 久久久久九九精品影院| 精品久久人妻av中文字幕| 欧美午夜精品久久久久免费视 | 狠狠精品久久久无码中文字幕| a级成人毛片久久| 欧美一级久久久久久久大片| 久久播电影网| 久久成人18免费网站| 欧美久久久久久午夜精品| 久久久黄片| 亚洲综合伊人久久综合| 囯产精品久久久久久久久蜜桃| 国内精品久久久久久中文字幕| 久久精品亚洲福利| 亚洲国产精品无码久久青草| 久久久久精品国产亚洲AV无码| 思思久久99热只有频精品66| 久久久国产乱子伦精品作者| 2020最新久久久视精品爱 | 国产精品欧美久久久久无广告 | 日本精品久久久久影院日本 | 精品久久久久久无码国产| 天天久久狠狠色综合| 国产香蕉久久精品综合网| 91久久成人免费|