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

            很麻煩的一個題目,最后一組數據打過去的,待修改。
            用BFS求最短路徑,用四維數組存所有的結果。載國王的情況只枚舉了國王身邊的八個點加上國王的位置(+-1),
            即騎士先到這個點國王也到這個點,然后他們一起走。這可能就是最后一組過不去的原因,以前只有19組測試數據,最后一個可能官方后來加的,我同學國王身邊+-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);  //國王坐標
                 while(fin>>column)
                 {
                                nNights++;
                                arr[nNights].y=int(column-'A'+1);
                                fin>>arr[nNights].x;//騎士坐標
                 }
            }

            void BFS(int x, int y) //求所有節點到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++)//計算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) );  //國王和騎士都(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 田兵 閱讀(331) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2010年5月>
            2526272829301
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久精品国产亚洲AV无码麻豆| 中文无码久久精品| Xx性欧美肥妇精品久久久久久| 99久久精品影院老鸭窝| 秋霞久久国产精品电影院| 亚洲精品NV久久久久久久久久| 一本色综合久久| 久久精品国产福利国产秒| 久久久久久曰本AV免费免费| 久久er热视频在这里精品| 国内精品久久久久影院老司| 久久久久四虎国产精品| 蜜臀久久99精品久久久久久小说| 精品一区二区久久| 亚洲中文精品久久久久久不卡| 嫩草伊人久久精品少妇AV| 免费精品久久久久久中文字幕| 97久久国产露脸精品国产| 久久国产福利免费| 丁香狠狠色婷婷久久综合| 国产亚洲精久久久久久无码77777| 东京热TOKYO综合久久精品| 国产精品久久久久久五月尺| 久久久久国产一区二区三区| 久久99精品久久久久久动态图| 久久99国产一区二区三区| 国产精品久久久久久影院| 蜜臀久久99精品久久久久久小说| 亚洲国产日韩欧美久久| 开心久久婷婷综合中文字幕| 国产精品女同一区二区久久| 亚洲狠狠综合久久| 国内精品久久久久国产盗摄| 99久久国产主播综合精品| 亚洲午夜精品久久久久久人妖| 亚洲AV日韩精品久久久久久久| 久久综合狠狠综合久久97色| 色婷婷噜噜久久国产精品12p| 久久国产精品成人片免费| 久久精品中文无码资源站 | 综合久久国产九一剧情麻豆|