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

            很麻煩的一個題目,最后一組數(shù)據(jù)打過去的,待修改。
            用BFS求最短路徑,用四維數(shù)組存所有的結(jié)果。載國王的情況只枚舉了國王身邊的八個點加上國王的位置(+-1),
            即騎士先到這個點國王也到這個點,然后他們一起走。這可能就是最后一組過不去的原因,以前只有19組測試數(shù)據(jù),最后一個可能官方后來加的,我同學國王身邊+-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 田兵 閱讀(324) 評論(0)  編輯 收藏 引用 所屬分類: USACO

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

            導航

            統(tǒng)計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久这里的只有是精品23| 久久精品国产亚洲AV无码麻豆| 久久国产亚洲精品麻豆| 久久久久无码专区亚洲av| 无码人妻久久一区二区三区免费丨| 狠狠色婷婷久久一区二区三区| 人妻精品久久久久中文字幕| 伊人久久大香线蕉综合影院首页| 久久精品成人免费国产片小草 | 丁香五月综合久久激情| 亚洲综合伊人久久综合| 久久国产乱子伦免费精品| 久久精品不卡| 88久久精品无码一区二区毛片 | 99精品国产99久久久久久97| 久久99精品久久久久久 | 99re这里只有精品热久久| 欧美精品乱码99久久蜜桃| 久久综合视频网| 国产AV影片久久久久久| 色欲综合久久中文字幕网| 麻豆久久久9性大片| 欧美日韩精品久久久免费观看| 精品国际久久久久999波多野| 亚洲精品国产综合久久一线| 色8激情欧美成人久久综合电| 国产精品一久久香蕉国产线看观看 | 热久久这里只有精品| 999久久久免费国产精品播放| 久久亚洲精品无码aⅴ大香| 久久99国产精品成人欧美| 久久免费国产精品| 2020国产成人久久精品| 久久人人爽人人澡人人高潮AV| 国产精品久久久久久| 久久国产亚洲高清观看| 久久亚洲精精品中文字幕| 伊人热人久久中文字幕| 国产精品久久久久久久久免费| 人妻精品久久久久中文字幕69| 亚洲精品蜜桃久久久久久|