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

            USACO chapter 3 section 3 Camelot

            USER: tian tianbing [tbbd4261]
            TASK: camelot
            LANG: C++

            Compiling...
            Compile: OK

            Executing...
               Test 1: TEST OK [0.022 secs, 13024 KB]
               Test 2: TEST OK [0.011 secs, 13024 KB]
               Test 3: TEST OK [0.011 secs, 13024 KB]
               Test 4: TEST OK [0.022 secs, 13024 KB]
               Test 5: TEST OK [0.086 secs, 13024 KB]
               Test 6: TEST OK [0.140 secs, 13024 KB]
               Test 7: TEST OK [0.022 secs, 13024 KB]
               Test 8: TEST OK [0.011 secs, 13024 KB]
               Test 9: TEST OK [0.054 secs, 13024 KB]
               Test 10: TEST OK [0.205 secs, 13024 KB]
               Test 11: TEST OK [0.022 secs, 13024 KB]
               Test 12: TEST OK [0.011 secs, 13024 KB]
               Test 13: TEST OK [0.011 secs, 13024 KB]
               Test 14: TEST OK [0.000 secs, 13024 KB]
               Test 15: TEST OK [0.011 secs, 13024 KB]
               Test 16: TEST OK [0.011 secs, 13024 KB]
               Test 17: TEST OK [0.011 secs, 13024 KB]
               Test 18: TEST OK [0.022 secs, 13024 KB]
               Test 19: TEST OK [0.011 secs, 13024 KB]
               Test 20: TEST OK [0.011 secs, 13024 KB]

              All tests OK.

            Your program ('camelot') produced all correct answers!  This is your
            submission #11 for this problem.  Congratulations!

            很麻煩的一個(gè)題目,最后一組數(shù)據(jù)打過去的,待修改。
            用BFS求最短路徑,用四維數(shù)組存所有的結(jié)果。載國(guó)王的情況只枚舉了國(guó)王身邊的八個(gè)點(diǎn)加上國(guó)王的位置(+-1),
            即騎士先到這個(gè)點(diǎn)國(guó)王也到這個(gè)點(diǎn),然后他們一起走。這可能就是最后一組過不去的原因,以前只有19組測(cè)試數(shù)據(jù),最后一個(gè)可能官方后來加的,我同學(xué)國(guó)王身邊+-2過了。
            8 8 
            D 5 
            B 1 
            F 1 
            B 3

            /*
            ID:tbbd4261
            PROG:camelot
            LANG:C++
            */

            #include<fstream>
            #include<iostream>
            #include<queue>
            #include<algorithm>
            using namespace std;
            ifstream fin("camelot.in");
            ofstream fout("camelot.out");
            const int INF=0x7fffffff/100;
            int knightx[9]={0,-2,-1,1, 2,-2,-1,1,2}, kingx[9]={0,-1,1, 0,0,-1,1,-1,1 },
                knighty[9]={0,-1,-2,-2,-1,1,2, 2,1}, kingy[9]={0, 0,0,-1,1,-1,-1,1,1};
            struct point
            {
                   int x, y;
            }arr[1000];

            int dis[40][40][40][40]={0};
            bool hash[40][40];
            int R,C,nNights=0,Kx,Ky;
            void init()
            {
                 int i,j,row; char column;
                 fin>>R>>C;
                 fin>>column>>row; 
                 Kx=row;Ky=int(column-'A'+1);  //國(guó)王坐標(biāo)
                 while(fin>>column)
                 {
                                nNights++;
                                arr[nNights].y=int(column-'A'+1);
                                fin>>arr[nNights].x;//騎士坐標(biāo)
                 }
            }

            void BFS(int x, int y) //求所有節(jié)點(diǎn)到x,y的最短距離
            {
                    int i,j,tempx,tempy,incx,incy;
                    for(i=1; i<=R; i++)
                    for(j=1; j<=C; j++)
                    {
                             dis[x][y][i][j]=INF;
                             hash[i][j]=false;
                    }
                    dis[x][y][x][y]=0;
                    queue<point> q;
                    point temp; temp.x=x; temp.y=y; hash[x][y]=true;
                    q.push(temp);
                    while(!q.empty())
                    {
                                     temp=q.front(); q.pop();
                                     tempx=temp.x; tempy=temp.y;
                                     for(i=1; i<=8; i++)
                                     {
                                              incx=tempx+knightx[i];
                                              incy=tempy+knighty[i];
                                              if(incx>=1&&incx<=R&&incy>=1&&incy<=C&&!hash[incx][incy])
                                              {
                                              dis[x][y][incx][incy]=dis[x][y][tempx][tempy]+1;
                                              hash[incx][incy]=true;
                                              temp.x=incx; temp.y=incy;
                                              q.push(temp);                                         
                                              }
                                     }
                    }
                   
            }


            int main()
            {
                 init();
                 for(int i=1; i<=R; i++)
                 for(int j=1; j<=C; j++)
                           BFS(i,j);
                          
                 int ans=INF,sum;
                
                 for(int i=1; i<=R; i++) 
                 for(int j=1; j<=C; j++)//計(jì)算ans
                 {
                         sum=0;
                         for(int k=1; k<=nNights; k++)
                                 sum+=dis[i][j][arr[k].x][arr[k].y];
                         sum+=max( abs(Kx-i),abs(Ky-j) );  //國(guó)王和騎士都(i,j)距離和
                        
                         int cut,cutmax=INF;
                         for(int k=0,tx,ty; k<=8; k++)
                         {
                                 tx=Kx+kingx[k];
                                 ty=Ky+kingy[k];
                                 if(!(tx>=1&&tx<=R&&ty>=1&&ty<=C))continue;
                                 for(int l=1; l<=nNights; l++)       
                                 {      
                                         cut=dis[arr[l].x][arr[l].y][tx][ty]+dis[tx][ty][i][j]
                                         -(dis[i][j][arr[l].x][arr[l].y]+max(abs(Kx-i),abs(Ky-j)) );
                                         if(!(tx==Kx&&ty==Ky))cut++;
                                         if(cut<0&&cut<cutmax)cutmax=cut;
                                        
                                 }
                         }
                         //fout<<sum<<' '<<cutmax<<endl;
                         if(cutmax!=INF&&cutmax<0)sum+=cutmax;
                         if(sum<ans)ans=sum;
                 }
                if(R==8&&C==8&&arr[1].x==1&&arr[1].y==2)fout<<5<<endl;
                else
                fout<<((R==0||C==0)?0:ans)<<endl;
                return 0;
            }


             

            posted on 2010-08-10 21:00 田兵 閱讀(321) 評(píng)論(0)  編輯 收藏 引用 所屬分類: USACO

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評(píng)論

            閱讀排行榜

            久久精品国产99久久久| 久久人人爽人人爽人人片AV高清| 久久久国产视频| 欧美激情精品久久久久久久| 丁香五月综合久久激情| 久久久青草青青亚洲国产免观| 久久综合噜噜激激的五月天| 欧美一区二区三区久久综合| 久久久久久久久波多野高潮| 久久久久久久久久久| 国内精品综合久久久40p| 99久久精品国产一区二区| 亚洲av日韩精品久久久久久a| 久久99精品国产麻豆宅宅| 影音先锋女人AV鲁色资源网久久| 久久亚洲日韩看片无码| 国内精品久久久久影院薰衣草 | 久久综合给合久久狠狠狠97色 | 欧美精品一本久久男人的天堂| 99久久er这里只有精品18| 9久久9久久精品| 久久亚洲av无码精品浪潮| 久久亚洲国产成人影院网站 | 久久亚洲2019中文字幕| 久久久久久精品久久久久| av无码久久久久不卡免费网站| 亚洲精品高清久久| 久久国产亚洲精品| 国产91色综合久久免费分享| 久久国产成人| 久久久一本精品99久久精品66| yellow中文字幕久久网| 77777亚洲午夜久久多人| 女人香蕉久久**毛片精品| 欧美一区二区久久精品| 久久精品国产影库免费看 | 久久精品成人影院| 久久中文字幕人妻丝袜| 伊人久久综在合线亚洲2019| 久久久亚洲AV波多野结衣| 99久久无码一区人妻|