• <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 田兵 閱讀(321) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久精品国产精品亚洲艾草网美妙| 国产欧美久久一区二区| 久久久国产一区二区三区| 久久91这里精品国产2020| 色综合久久88色综合天天 | 香蕉aa三级久久毛片| 久久精品九九亚洲精品| 欧美亚洲国产精品久久蜜芽 | 久久综合一区二区无码| 日产久久强奸免费的看| 亚洲国产精品无码久久久不卡| 久久发布国产伦子伦精品| 久久久久国产一区二区 | 日本人妻丰满熟妇久久久久久| 久久精品国产亚洲AV电影| 久久亚洲精品无码播放| 97久久精品无码一区二区天美| 午夜视频久久久久一区 | 亚洲日本va午夜中文字幕久久| 色8久久人人97超碰香蕉987| 久久国产成人| 久久精品国产亚洲AV高清热| 亚洲欧美精品一区久久中文字幕| 嫩草影院久久国产精品| 色偷偷久久一区二区三区| 一日本道伊人久久综合影| 国产午夜福利精品久久| 久久综合久久综合九色| 久久久久无码精品国产不卡| 国产亚洲精品久久久久秋霞| 久久久久国产精品嫩草影院| 99久久国产免费福利| 国产成年无码久久久久毛片| 亚洲熟妇无码另类久久久| 久久99热这里只频精品6| 久久久亚洲精品蜜桃臀| 久久精品国产亚洲7777| 久久夜色撩人精品国产小说| 亚洲成av人片不卡无码久久| 久久综合色之久久综合| 久久综合亚洲色HEZYO社区|