骑士走的方式用普通的BFS，保存每个骑士的最短路径。然后枚举每个骑士在每个点接国王，计算路径即可。
相当麻烦的考验耐心的题目。
/*
ID:bysen
LANG:C++
PROG:camelot
*/
#include<stdio.h>
#include<queue>
#define MAXR 31
#define MAXC 27
#define INF 0x0FFFFFFF
using namespace std;struct K
{int r,c;
}knight[MAXR*MAXC];K king;struct bfsK
{int r,c,step;
};int knightnum;
int remap[MAXR*MAXR][MAXR][MAXC];
int R,C;int max( int a,int b ){ return a>b?a:b; }//坐标映射
int getR( int num ){ return num/C+1; }
int getC( int num ){ return num%C+1; }
int getNum( int r,int c ){ return (r-1)*C+c-1; }
int d[8][2]={ {-2,+1},{-1,+2},{+1,+2},{+2,+1},{+2,-1},{+1,-2},{-1,-2},{-2,-1} };void init()
{freopen( "camelot.in","r",stdin );freopen( "camelot.out","w",stdout );scanf( "%d %d\n",&R,&C );char c;int r;for( int k=0;k<MAXR*MAXC;k++ )for( int i=0;i<=R;i++ )for( int j=0;j<=C;j++ )remap[k][i][j]=INF;scanf( "%c %d",&c,&r );king.r=r;king.c=c-'A'+1;knightnum=0;while( scanf( "%c",&c )!=EOF ){if( c<'A' || c>'Z' )continue;scanf( "%d\n",&r );knight[knightnum].r=r;knight[knightnum].c=c-'A'+1;knightnum++;}/*for( int i=0;i<knightnum;i++ )printf( "%d: %d %d\n",i,knight[i].r,knight[i].c );*/
}void bfs( int num )
{int r,c,x,y;bool flag[MAXR][MAXC]={false};r=getR(num);c=getC(num);bfsK k;k.r=r;k.c=c;k.step=0;queue<bfsK>myQueue;myQueue.push(k);flag[k.r][k.c]=true;remap[num][k.r][k.c]=0;while( !myQueue.empty() ){bfsK cur=myQueue.front();myQueue.pop();r=cur.r;c=cur.c;for( int i=0;i<8;i++ ){x=d[i][0];y=d[i][1];if( r+x>=1 && r+x<=R && c+y>=1 && c+y<=C && flag[r+x][c+y]==false ){flag[r+x][c+y]=true;bfsK tmp;tmp.r=r+x;tmp.c=c+y;tmp.step=cur.step+1;remap[num][tmp.r][tmp.c]=tmp.step;myQueue.push(tmp);}}}
}void record( )
{for( int k=0;k<R*C;k++ )bfs( k );/*for( int k=0;k<R*C;k++ ){printf( "%d\n",k );for( int i=1;i<=R;i++ ){for( int j=1;j<=C;j++ )printf( "%d ",remap[k][i][j] );printf( "\n" );}}for( int k=0;k<knightnum;k++ ){printf( "%d %d:\n",knight[k].r,knight[k].c );printf( "%d\n",getNum(knight[k].r,knight[k].c) );for( int i=1;i<=R;i++ ){for( int j=1;j<=C;j++ )printf( "%d ",remap[getNum(knight[k].r,knight[k].c)][i][j] );printf( "\n" );}}*/
}void enumwork()
{int ans=INF;int sum[MAXR][MAXC]={0};for( int k=0;k<knightnum;k++ ){int remapnum=getNum(knight[k].r,knight[k].c);for( int i=1;i<=R;i++ )for( int j=1;j<=C;j++ )sum[i][j]+=remap[remapnum][i][j];}/*for( int i=1;i<=R;i++ ){for( int j=1;j<=C;j++ )printf( "%d ",sum[i][j]);printf( "\n" );}*/for( int i=1;i<=R;i++ )for( int j=1;j<=C;j++ ){//枚举最终集合点 int enumnum=getNum(i,j);if( ans>sum[i][j] ){int knightAllStep=sum[i][j];int kingstep;//枚举 哪个骑士来接国王 for( int k=0;k<knightnum;k++ ){int NoKnight=getNum(knight[k].r,knight[k].c);//骑士在预存图中的编号int knightRideStep;//接国王的骑士走的步数 knightAllStep=sum[i][j]-remap[NoKnight][i][j];//除了这个骑士外其他骑士走的步数//枚举骑士国王的碰头地点for( int a=1;a<=R;a++ )for( int b=1;b<=C;b++ ){kingstep=max( abs(king.r-a),abs(king.c-b) );knightRideStep=remap[NoKnight][a][b]+remap[getNum(a,b)][i][j];//骑士从源点走向与王汇合点+从汇合点到所有人的集合点;if( ans>kingstep+knightRideStep+knightAllStep )ans=kingstep+knightRideStep+knightAllStep;}}}}printf( "%d\n",ans );
}int main()
{init();if( knightnum==0 ){printf( "0\n" );return 0;}record();//对每个位置进行一次enumwork();//枚举工作 return 0;
}