floyd+枚举. 题目来源:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1178 我们将每一个格子看作一个结点,将该结点与附近的骑士能一步到达的结点连一条边.然后用floyd求出每对结点间的最段路径,这就是骑士从一个格子走到另外一个格子的最小步数.对于国王我们可以直接用坐标来求出他通往任意两个格子间的最小步数. 然后枚举他们的汇聚点和国王与骑士的汇合点,再枚举是哪个骑士和国王回合.取最小的那个值.详细见代码:
#include<iostream>
#include<cmath>
using namespace std;
const int inf=100000000;
int location[64],knight[64][64];
int kn_dir[8][2]=
{-2,-1,-2,1,-1,-2,-1,2,1,-2,1,2,2,-1,2,1};
char str[130];
void floyd()
{
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][j]>knight[i][k]+knight[k][j])
knight[i][j]=knight[i][k]+knight[k][j];
}
}
void Init()
{
int i,j;
for(i=0;i<64;i++)
for(j=0;j<64;j++)
{
if(i==j) knight[i][j]=0;
else knight[i][j]=inf;
}
for(i=0;i<64;i++)
{
for(j=0;j<8;j++)
{
int x=i/8+kn_dir[j][0];
int y=i%8+kn_dir[j][1];
if(x>=0&&x<8&&y>=0&&y<8)
{
knight[i][x*8+y]=1;
}
}
}
floyd();
}
int main()
{
int i,j,k,num,ans=inf;
Init();
scanf("%s",str);
for(i=0,num=0;str[i];i+=2)
{
location[num++]=8*(str[i+1]-'1')+(str[i]-'A');
}
for(i=0;i<64;i++)
for(j=0;j<64;j++)
{
int xx=abs(location[0]/8-j/8);
int yy=abs(location[0]%8-j%8);
int king_len=xx>yy ? xx:yy;
int knight_len=inf;
for(k=1;k<num;k++)
{
int temp=0;
for(int v=1;v<num;v++)
if(v!=k)
{
temp+=knight[location[v]][i];
}
temp+=knight[location[k]][j]+knight[j][i];
if(knight_len>temp) knight_len=temp;
}
if(knight_len==inf&&king_len<ans) ans=king_len;
else if(king_len+knight_len<ans) ans=king_len+knight_len;
}
printf("%d\n",ans);
//system("pause");
return 0;
}
posted on 2010-08-20 16:34
wuxu 阅读(212)
评论(0) 编辑 收藏 引用 所属分类:
图论