青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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個國王和若干個騎士,要把國王和每個騎士移動到同一個格子內(nèi),問需要移動的最小步數(shù)是多少。如果國王和騎士走到同一個格子里,可以由騎士帶著國王一起移動。
    枚舉棋盤上的64個點作為終點,對于每一個假定的終點,再枚舉這64個點作為國王和某個騎士相遇的點,最后求出需要移動的最小步數(shù)。其中根據(jù)騎士和國王移動的特點可以預(yù)處理出從1個點到另外1個點所需的最小移動次數(shù),也可用搜索。
#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 極限定律 閱讀(2355) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

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

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(10)

隨筆分類

隨筆檔案

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            国产精品午夜电影| 国产精品国产a| 亚洲免费电影在线观看| 亚洲成色精品| 欧美国产大片| 亚洲午夜一区二区三区| 亚洲免费在线| 亚洲高清视频中文字幕| 亚洲精品在线看| 国产精品一区二区在线| 一本色道久久综合狠狠躁篇的优点| 艳妇臀荡乳欲伦亚洲一区| 国产精品夜色7777狼人| 欧美成人一区二免费视频软件| 欧美日韩国产va另类| 香蕉久久一区二区不卡无毒影院| 久久国产黑丝| 亚洲深爱激情| 久久久久久电影| 亚洲综合导航| 欧美大片免费看| 欧美有码在线视频| 欧美久久久久久蜜桃| 久久av老司机精品网站导航| 欧美va亚洲va日韩∨a综合色| 亚洲一区精品视频| 美女性感视频久久久| 亚洲免费福利视频| 久久精品首页| 午夜日韩av| 欧美日韩伦理在线免费| 久久久精品999| 欧美日韩国内| 欧美mv日韩mv国产网站| 国产精品网站在线观看| 亚洲国内高清视频| 在线日韩欧美| 欧美中文在线观看| 宅男在线国产精品| 欧美丰满高潮xxxx喷水动漫| 久久午夜视频| 国产精品亚洲综合| 亚洲视频福利| 亚洲精品一区二区三区福利| 久久国产精品99国产精| 亚洲欧美日韩国产精品 | 久久精品亚洲| 欧美国产日韩视频| 乱码第一页成人| 国产亚洲一区二区三区在线观看| 一区二区三区 在线观看视频| 亚洲黑丝一区二区| 久久精品视频免费观看| 久久噜噜亚洲综合| 国产一区二区三区av电影| 亚洲一区二区综合| 午夜在线精品偷拍| 国产精品网曝门| 欧美在线免费观看| 开心色5月久久精品| 国一区二区在线观看| 久久本道综合色狠狠五月| 久久久天天操| 在线观看三级视频欧美| 久久亚裔精品欧美| 亚洲第一精品在线| 99re这里只有精品6| 欧美另类在线播放| 中文在线不卡| 久久精品免费| 亚洲成人在线视频网站| 免费成人性网站| 亚洲精品在线观看视频| 亚洲伊人网站| 国产欧美va欧美不卡在线| 午夜精品亚洲| 欧美成人午夜视频| 一本色道婷婷久久欧美| 国产精品久久国产三级国电话系列| 亚洲一区二区三区精品视频| 久久精品最新地址| 亚洲片国产一区一级在线观看| 欧美激情久久久久| 中国亚洲黄色| 另类av一区二区| 在线综合亚洲欧美在线视频| 国产精品一二一区| 免费不卡视频| 亚洲欧美在线aaa| 欧美96在线丨欧| 亚洲天堂成人在线视频| 国产午夜亚洲精品不卡| 欧美成人免费va影院高清| av不卡免费看| 欧美成人精品在线观看| 在线视频你懂得一区| 韩国av一区二区三区四区| 欧美日韩国产片| 久久免费视频在线| 一区二区日韩欧美| 亚洲电影欧美电影有声小说| 亚洲欧美春色| 日韩网站免费观看| 国产真实乱偷精品视频免| 欧美日韩午夜在线视频| 久久久久久久999| 亚洲一区中文| 亚洲精品欧美日韩| 免费亚洲网站| 久久精品中文字幕一区| 亚洲一区三区视频在线观看| 亚洲大片在线观看| 国产欧美精品日韩精品| 欧美久久久久久蜜桃| 久久亚洲视频| 久久久水蜜桃| 欧美尤物一区| 国产精品午夜电影| 欧美精品一区二区精品网| 久久婷婷av| 久久精品国产精品| 欧美中文字幕视频| 午夜在线成人av| 亚洲淫性视频| 亚洲色图综合久久| 日韩视频一区二区三区| 亚洲国产精品久久久久久女王 | 1024亚洲| 激情视频一区二区| 黄色国产精品| 136国产福利精品导航网址应用| 国产色视频一区| 国产日韩欧美二区| 国产色综合久久| 国产亚洲欧美激情| 国产精品专区一| 国产视频一区在线观看| 国产伦理一区| 激情视频一区二区| 亚洲第一黄网| 亚洲黄色成人久久久| 亚洲第一区在线观看| 在线观看免费视频综合| **性色生活片久久毛片| 精品999成人| 亚洲二区三区四区| 亚洲欧洲日本国产| 一本大道久久精品懂色aⅴ| 一本大道久久a久久精二百| 亚洲少妇最新在线视频| 午夜性色一区二区三区免费视频| 亚洲欧美日韩一区二区三区在线观看 | 国产亚洲人成a一在线v站| 国产在线观看一区| 亚洲黄网站黄| 亚洲免费小视频| 久久久久久久久久久一区 | 欧美 亚欧 日韩视频在线| 亚洲高清色综合| 亚洲午夜av电影| 久久精品亚洲热| 久久亚洲电影| 欧美调教视频| 国内外成人免费激情在线视频 | 国产日产欧产精品推荐色 | 午夜日韩av| 久久综合中文色婷婷| 欧美精品一线| 国产精品推荐精品| 激情偷拍久久| 中日韩视频在线观看| 久久高清一区| 最新中文字幕亚洲| 亚洲一区尤物| 欧美精品videossex性护士| 国产精品午夜电影| 亚洲日韩中文字幕在线播放| 性欧美大战久久久久久久免费观看 | 亚洲国产日韩综合一区| 亚洲午夜精品久久| 麻豆国产精品777777在线| 亚洲毛片在线| 久久噜噜噜精品国产亚洲综合| 欧美午夜美女看片| 亚洲国产精品成人一区二区| 香蕉成人久久| 亚洲人成免费| 久久久无码精品亚洲日韩按摩| 国产精品毛片高清在线完整版| 91久久精品久久国产性色也91| 欧美一区二区在线免费观看| 亚洲激情校园春色| 久久久久久久久综合| 国产精品久久77777| 亚洲肉体裸体xxxx137| 久久国产精品久久精品国产| 亚洲免费av网站| 欧美大片在线看| 玉米视频成人免费看| 欧美自拍丝袜亚洲|