#include <iostream>
#include <string.h>
#include <cmath>
#include <stdlib.h>
using namespace std;

const int MAX=0x7fffffff/2;
char str[200];
int king[1][2];
int dis[65][65], disking[65][65];
int knight[65][2];int numknight;
const int str1[]={-2,-2,-1,-1,1,1,2,2},str2[]={-1,1,-2,2,-2,2,-1,1};

bool legal(int x,int y)
{
    return (x>=1&&x<=8&&y>=1&&y<=8);
}
void floyed()
{   
    int i,j,k;
    for(k=1;k<=64;k++)
    for(i=1;i<=64;i++)
    for(j=1;j<=64;j++)
    if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];   

    for(k=1;k<=64;k++)
    for(i=1;i<=64;i++)
    for(j=1;j<=64;j++)
    if(disking[i][k]+disking[k][j]<disking[i][j]) disking[i][j]=disking[i][k]+disking[k][j];
}
void inition()
{
    int i,j,k,u;
    for(i=1;i<=64;i++)
    for(j=1;j<=64;j++)
    if(i==j)
    {dis[i][j]=0;disking[i][j]=0;}
    else
    {
        dis[i][j]=MAX;
        dis[j][i]=MAX;
        disking[i][j]=MAX;
        disking[j][i]=MAX;
    }
    for(i=1;i<=64;i++)
    {
        int x=i/8+1,y=i-i/8*8;if(i%8==0)x--;if(y==0) y=8; 
        for(j=0;j<8;j++)
        if(legal(x+str1[j],y+str2[j]))
        {
            dis[(x-1)*8+y ][ (x+str1[j]-1)*8+y+str2[j]]=1;
            dis[ (x+str1[j]-1)*8+y+str2[j]][(x-1)*8+y ]=1;
        }
        for(k=-1;k<=1;k++)
        for(u=-1;u<=1;u++)
        if(k==0&&u==0) disking[k][u]=0;
        else
        {
            if(legal(x+k,y+u))
            {
                disking[i][(x+k-1)*8+y+u]=1;
                disking[(x+k-1)*8+y+u][i]=1;
            }
        }
    }
    floyed(); 
}


void f()
{
    int i,j,k,u;int ans=MAX;int sum;
    for(i=1;i<=64;i++) // node=    i/8+1  , (i-1)%8+1 循环64个可能的目标点。
    {  
        for(j=1;j<=64;j++) //选被选的骑士跟头领的汇合点
        {  
            for(k=1;k<numknight;k++) //选可能带头领的骑士
            {
                sum=disking[king[0][0]*8-8+king[0][1]][j];
                for(u=1;u<numknight;u++)
                {
                    if(u==k)
                    sum+=dis [knight[u][0]*8-8+knight[u][1]][j] + dis[j][i];
                    else
                    sum+=dis[knight[u][0]*8-8+knight[u][1]][i];
                }
                if(ans>sum) ans=sum;
            }
        }
    }
    printf("%d\n",ans);
}
int main()
{
    inition();
    while(cin>>str)
    {
        numknight=1;
        int len=strlen(str);
        if(len==2) {cout<<0<<endl;continue;}
        else
        {
          for(int i=0;i<len;i+=2)
          if(i==0){king[0][0]=str[i]-'A'+1;king[0][1]=str[i+1]-'0';}
          else {knight[numknight][0]=str[i]-64;knight[numknight][1]=str[i+1]-'0';numknight++;} 
          f();
        }
    }
    return 0;
}

• Re:调试了2天终于...犯尽了各种错误... (43) ACM_Micro_C 2009-05-30 15:31:58
  • Re:调试了2天终于...犯尽了各种错误... (4) ss08zhangchi 2011-02-16 15:45:37
  • Re:调试了2天终于...犯尽了各种错误... (9) bingshen 2011-02-16 19:16:52