热烈庆祝CZTCODE累计文章100篇！
Camelot
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 8×8 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’s 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
我的代码
预处理：定义两点之间的距离为将棋子从一个点移动到另一个点的次数。使用Floyd算法求出棋盘一点到其余所有点的最短距离。要求两种行走方式下的最短距离，第一种是骑士的日字走法，还有一个是国王的周围格子的走法。
本题思路是选择一个骑士在某处带上国王，之后所有骑士都一次性走到终点。总距离为：某个带上国王的骑士与国王各自到达集合点的距离+该骑士和国王从集合点前往终点的距离+剩余骑士到达终点的距离。
骑士需要和国王选择一个集合点（上马点），这个点的位置不能确定；所有骑士的终点也不确定。这两个位置都需要遍历，还好棋盘大小只有64格大小。最后遍历的过程是：选择终点->选择集合点->选择和国王集合的骑士->计算距离。
直观的代码如下：
for (int i=0;i<64;i++)
//终点
{
for (int j=0;j<64;j++)
//上马点
{
for (int k=0;k<num-1;k++)
//骑士
{
int temp=0;
for (int m=0;m<num-1;m++)
{
if (m!=k)
{
temp+=wknight[knights[m]][i];
}
else
{
temp+=wknight[knights[m]][j]+wknight[j][i]+wking[king][j];
}
}
if (temp<ans) ans=temp;
}
}
}其中选择骑士的部分可以少一个循环：
for (int i=0;i<64;i++)
//终点
{
for (int j=0;j<64;j++)
//上马点
{
int sum=0;
for (int k=0;k<num-1;k++)
{
sum+=wknight[knights[k]][i];
}
for (int k=0;k<num-1;k++)
{
int temp;
temp=sum-wknight[knights[k]][i]+wknight[knights[k]][j]+wknight[j][i]+wking[king][j];
if (temp<ans) ans=temp;
}
}
}完整代码：
#include<stdio.h>
#include<string.h>
const int inf=0x3f3f3f3f;
int wknight[65][65];//记录按照骑士走法的最短距离
int wking[65][65];//记录按照国王走法的最短距离
int dknight[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};
int dking[8][2]= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
int knights[65];//记录骑士位置
int king;//记录国王位置
int num=0;
int ans=inf;
int check(int x,int y)
{
if (x>=0&&x<8&&y>=0&&y<8) return 1;
else return 0;
}
int min(int x,int y)
{
return x<y?x:y;
}
void initiate()
{
for (int i=0;i<8;i++)
{
for (int j=0;j<8;j++)
{
wknight[i*8+j][i*8+j]=0;
for (int k=0;k<8;k++)
{
if (check(i+dknight[k][0],j+dknight[k][1]))
{
wknight[i*8+j][(i+dknight[k][0])*8+j+dknight[k][1]]=1;
wknight[(i+dknight[k][0])*8+j+dknight[k][1]][i*8+j]=1;
}
}
}
}
for (int i=0;i<8;i++)
{
for (int j=0;j<8;j++)
{
wking[i*8+j][i*8+j]=0;
for (int k=0;k<8;k++)
{
if (check(i+dking[k][0],j+dking[k][1]))
{
wking[i*8+j][(i+dking[k][0])*8+j+dking[k][1]]=1;
wking[(i+dking[k][0])*8+j+dking[k][1]][i*8+j]=1;
}
}
}
}
}
void floyd()
{
for (int k=0;k<64;k++)
{
for (int i=0;i<64;i++)
{
for (int j=0;j<64;j++)
{
wknight[i][j]=min(wknight[i][j],wknight[i][k]+wknight[k][j]);
}
}
}
for (int k=0;k<64;k++)
{
for (int i=0;i<64;i++)
{
for (int j=0;j<64;j++)
{
wking[i][j]=min(wking[i][j],wking[i][k]+wking[k][j]);
}
}
}
}
int main()
{
char c;
int x,y;
memset(wknight,inf,sizeof(wknight));
memset(wking,inf,sizeof(wking));
initiate();//初始化
floyd();//生成最短距离
while (scanf("%c%d",&c,&y)==2)
{
x=c-'A';
if (num==0)
{
king=x*8+y-1;
num++;
}
else
{
knights[num-1]=x*8+y-1;
num++;
}
}
for (int i=0;i<64;i++)
//终点
{
for (int j=0;j<64;j++)
//上马点
{
int sum=0;
for (int k=0;k<num-1;k++)
{
sum+=wknight[knights[k]][i];
}
for (int k=0;k<num-1;k++)
{
int temp;
temp=sum-wknight[knights[k]][i]+wknight[knights[k]][j]+wknight[j][i]+wking[king][j];
if (temp<ans) ans=temp;
}
/*
for (int k=0;k<num-1;k++)
//骑士
{
int temp=0;
for (int m=0;m<num-1;m++)
{
if (m!=k)
{
temp+=wknight[knights[m]][i];
}
else
{
temp+=wknight[knights[m]][j]+wknight[j][i]+wking[king][j];
}
}
if (temp<ans) ans=temp;
}
*/
}
}
printf("%d",ans);
return 0;
}反思
这一题主要是很巧妙得使用Floyd算法将最短距离求了出来，之后枚举点的思路其实很简单。
ctrl+z是在windows命令行中输入EOF。