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

            POJ 1178 Camelot Floyd算法+枚舉

            Description

            Centuries ago, King Arthur and the Knights of the Round Table used to meet every year on New Year's Day to celebrate their fellowship. In remembrance of these events, we consider a board game for one player, on which one king and several knight pieces are placed at random on distinct squares.
            The Board is an 8x8 array of squares. The King can move to any adjacent square, as shown in Figure 2, as long as it does not fall off the board. A Knight can jump as shown in Figure 3, as long as it does not fall off the board.

            During the play, the player can place more than one piece in the same square. The board squares are assumed big enough so that a piece is never an obstacle for other piece to move freely.
            The player抯 goal is to move the pieces so as to gather them all in the same square, in the smallest possible number of moves. To achieve this, he must move the pieces as prescribed above. Additionally, whenever the king and one or more knights are placed in the same square, the player may choose to move the king and one of the knights together henceforth, as a single knight, up to the final gathering point. Moving the knight together with the king counts as a single move.

            Write a program to compute the minimum number of moves the player must perform to produce the gathering.

            Input

            Your program is to read from standard input. The input contains the initial board configuration, encoded as a character string. The string contains a sequence of up to 64 distinct board positions, being the first one the position of the king and the remaining ones those of the knights. Each position is a letter-digit pair. The letter indicates the horizontal board coordinate, the digit indicates the vertical board coordinate.

            0 <= number of knights <= 63

            Output

            Your program is to write to standard output. The output must contain a single line with an integer indicating the minimum number of moves the player must perform to produce the gathering.

            Sample Input

            D4A3A8H1H8

            Sample Output

            10

            Source


                棋盤上有1個國王和若干個騎士,要把國王和每個騎士移動到同一個格子內,問需要移動的最小步數是多少。如果國王和騎士走到同一個格子里,可以由騎士帶著國王一起移動。
                枚舉棋盤上的64個點作為終點,對于每一個假定的終點,再枚舉這64個點作為國王和某個騎士相遇的點,最后求出需要移動的最小步數。其中根據騎士和國王移動的特點可以預處理出從1個點到另外1個點所需的最小移動次數,也可用搜索。
            #include <iostream>
            using namespace std;

            const int inf = 100000;
            char str[150];
            int k[64],king[64][64],knight[64][64];
            int move1[8][2]={-1,-1,-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1};
            int move2[8][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2};

            void init(){
                
            int i,j,x,y,tx,ty;
                
            for(i=0;i<64;i++)
                    
            for(j=0;j<64;j++)
                        
            if(i==j) king[i][j]=knight[i][j]=0;
                        
            else king[i][j]=knight[i][j]=inf;
                
            for(i=0;i<64;i++){
                    x
            =i/8,y=i%8;
                    
            for(j=0;j<8;j++){
                        tx
            =x+move1[j][0],ty=y+move1[j][1];
                        
            if(tx>=0 && ty>=0 && tx<8 && ty<8)
                            king[i][
            8*tx+ty]=1;
                    }

                }

                
            for(i=0;i<64;i++){
                    x
            =i/8,y=i%8;
                    
            for(j=0;j<8;j++){
                        tx
            =x+move2[j][0],ty=y+move2[j][1];
                        
            if(tx>=0 && ty>=0 && tx<8 && ty<8)
                            knight[i][
            8*tx+ty]=1;
                    }

                }

            }

            void floyd1(){
                
            int i,j,k;
                
            for(k=0;k<64;k++)
                    
            for(i=0;i<64;i++)
                        
            for(j=0;j<64;j++)
                            
            if(king[i][k]+king[k][j]<king[i][j])
                                king[i][j]
            =king[i][k]+king[k][j];
            }

            void floyd2(){
                
            int i,j,k;
                
            for(k=0;k<64;k++)
                    
            for(i=0;i<64;i++)
                        
            for(j=0;j<64;j++)
                            
            if(knight[i][k]+knight[k][j]<knight[i][j])
                                knight[i][j]
            =knight[i][k]+knight[k][j];
            }

            int main(){
                
            int i,j,l,cnt,pos,sum,ans,len,t1,t2;
                init();
                floyd1();
                floyd2();
                
            while(scanf("%s",str)!=EOF){
                    len
            =strlen(str);
                    pos
            =(str[0]-'A')+(str[1]-'1')*8;
                    cnt
            =(len-2)/2;
                    
            if(cnt==0){
                        printf(
            "0\n");
                        
            continue;
                    }

                    
            for(i=0,j=2;i<cnt;i++,j+=2)
                        k[i]
            =(str[j]-'A')+(str[j+1]-'1')*8;
                    
            for(ans=inf,i=0;i<64;i++){
                        
            for(sum=l=0;l<cnt;l++)
                            sum
            +=knight[k[l]][i];
                        
            for(j=0;j<64;j++){
                            t1
            =king[pos][j];
                            
            for(t2=inf,l=0;l<cnt;l++)
                                t2
            =min(t2,knight[k[l]][j]+knight[j][i]-knight[k[l]][i]);
                            ans
            =min(ans,sum+t1+t2);
                        }

                    }

                    printf(
            "%d\n",ans);
                }

                
            return 0;
            }

            posted on 2009-07-02 23:57 極限定律 閱讀(2338) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            精品久久久久久99人妻| 亚洲精品国产第一综合99久久| 麻豆精品久久久久久久99蜜桃| 久久受www免费人成_看片中文| 久久久无码精品亚洲日韩京东传媒| 99久久夜色精品国产网站| 91久久婷婷国产综合精品青草| 色偷偷888欧美精品久久久| 久久99精品久久久久久不卡| 性做久久久久久久久老女人| 久久国产免费观看精品3| 国产高清美女一级a毛片久久w| 亚洲国产一成人久久精品| 66精品综合久久久久久久| 无码八A片人妻少妇久久| 久久99久久99精品免视看动漫| 亚洲国产精品婷婷久久| 欧美成人免费观看久久| 久久精品嫩草影院| 久久久久人妻精品一区二区三区 | 久久久久久夜精品精品免费啦 | 99久久人妻无码精品系列蜜桃| 精品久久人人爽天天玩人人妻| 久久天天躁狠狠躁夜夜网站 | 欧美精品福利视频一区二区三区久久久精品| 国内精品久久久久影院老司| 狠狠色伊人久久精品综合网| 狠狠色丁香婷婷综合久久来| 一本久久a久久精品vr综合| 久久影院亚洲一区| 欧美粉嫩小泬久久久久久久| 国产精品美女久久久久AV福利| 久久久久综合网久久| 久久精品国产亚洲AV嫖农村妇女| 久久久久久久波多野结衣高潮 | 久久伊人精品一区二区三区| 久久久久一本毛久久久| 久久久久无码精品| 一级做a爰片久久毛片毛片| 色婷婷久久久SWAG精品| 深夜久久AAAAA级毛片免费看|