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

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产香蕉97碰碰久久人人| 久久久久久精品久久久久| 久久精品国产99久久无毒不卡| 国产精品对白刺激久久久| 久久国产美女免费观看精品| 精品久久久久久久国产潘金莲| 久久精品中文字幕无码绿巨人| 激情久久久久久久久久| 亚洲AV无码久久精品蜜桃| 国产99久久久久久免费看| 99久久国产精品免费一区二区| 青青草原综合久久| 久久亚洲精品成人av无码网站| 久久精品国产色蜜蜜麻豆| 亚洲AV成人无码久久精品老人| 久久久这里有精品中文字幕| 狠狠狠色丁香婷婷综合久久五月| 亚洲精品99久久久久中文字幕| 久久综合九色综合97_久久久| 久久精品日日躁夜夜躁欧美| 久久久无码精品亚洲日韩软件| 人人狠狠综合久久亚洲88| 伊人久久大香线蕉AV色婷婷色| 久久综合狠狠综合久久97色| 欧美亚洲国产精品久久蜜芽| 97久久超碰国产精品旧版| 亚洲精品tv久久久久久久久| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 久久久久久国产精品无码超碰| 亚洲国产综合久久天堂| 亚洲欧美国产日韩综合久久| 久久99精品久久久久久9蜜桃| 国产精品无码久久久久| 久久精品无码一区二区三区免费 | 久久九九精品99国产精品| 亚洲精品无码久久久久去q | 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 久久香蕉综合色一综合色88| 久久午夜电影网| 久久久久久无码国产精品中文字幕 | 99久久www免费人成精品|