• <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) //求所有節(jié)點到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 田兵 閱讀(325) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統(tǒng)計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            亚洲精品国精品久久99热| 91久久精一区二区三区大全| 国产视频久久| 久久久久亚洲AV无码专区首JN| 亚洲人成无码www久久久| 性欧美丰满熟妇XXXX性久久久 | 久久久久久精品免费免费自慰| 久久狠狠爱亚洲综合影院| 久久国产亚洲精品无码| 国产成人久久久精品二区三区| 国产欧美久久久精品影院| 久久ww精品w免费人成| 久久伊人色| 国产亚洲综合久久系列| 久久精品国产亚洲av麻豆小说| 91精品婷婷国产综合久久| 久久狠狠爱亚洲综合影院| 久久久久免费视频| 亚洲一区中文字幕久久| 午夜精品久久久久久中宇| 性高朝久久久久久久久久| 99精品伊人久久久大香线蕉| 久久无码AV中文出轨人妻| 激情综合色综合久久综合| 久久精品亚洲日本波多野结衣| 亚洲人成无码网站久久99热国产| 久久国产精品久久国产精品| 亚洲色欲久久久综合网| 久久中文字幕人妻熟av女| 亚洲国产精品无码久久九九| 久久久久人妻一区精品| 天天爽天天爽天天片a久久网| 国产亚洲精品美女久久久| 日韩av无码久久精品免费| 无遮挡粉嫩小泬久久久久久久| 久久人人青草97香蕉| 久久婷婷五月综合成人D啪 | 无码精品久久久天天影视| 精品熟女少妇AV免费久久| 人妻丰满AV无码久久不卡| 久久亚洲精品人成综合网|