骑士走的方式用普通的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; }