USACO Training Section 3.3 Camelot

英文原题  中文题译

大意：在棋盘上方若干个骑士和一个国王，要让他们汇聚到一个格子上，其中骑士带上国王走这样国王上马之后不计代价。问，汇集他们的最小代价是多少步。（骑士走马步，国王走任意一相邻格）。

国王到每个点的距离是已知的，即为行列差之和。因此，只要考虑骑士：

对棋盘上的每个格子作为汇聚点做枚举（26*30)。从该节点出发作宽度优先搜索，如果有骑士所在的格子不能到达，则放弃。否则，宽搜时记录的轨迹可得到每个骑士到汇集点的路径，让国王到路径上最近的格子与骑士回合，计算得到使用该汇集点的总代价。

这个算法似乎有问题，骑士可以为了捎带国王而绕路，或者选择走不同的最优路径。我们无法保证在上面记录路径的时候记录的是最靠近国王的那个。

因此，不记录路径，而记录点对之间的最短距离。首先计算出按骑士走法的棋盘上任意两点间的最短距离，之后，对每个汇聚点，首先考虑国王的走法，是否需要骑士携带，或者自己走到汇聚点：设汇聚点为H，国王位置为K，有N[i]个骑士，则若有骑士在位置P接应国王，那么其代价为Kdis(K,P)+min{Ndis(N[i],P)+Ndis(P,H)-Ndis(N[i],H)}，在这个代价中找最小的P和H，即为国王上马的最小代价，再与国王自己走到目标点的代价Kdis(K,H)比较取其小的。

如果P的选取范围是全棋盘，那么能确保得到最优解。不过这样会超时（时间代价为O(m^2*n^2*k)其中m,n为行列数，k为骑士数，而骑士最多为m*n，则代价为O(N^3)(N=m*n为棋盘大小）。修改为国王周边正负2格，程序通过。不过这很显然是不能保证最优解，不过，考虑到棋盘本身不大，也就这样吧。

最后，这个方法的时间和空间复杂度都是可以优化的，比如：
1. 考虑棋盘的对称性，计算最小距离矩阵时只需计算1/4即可。
2. 数组下标直接引用修改为按指针访问，至少可以提升一半的效率。
3. 棋盘按二维数组访问可修改为展开成一维。有意思的是，展开成一维之后，会发现这和3.2.6极为相似。事实上，如果没有国王，只有骑士，这两个题就一个是在加权图，一个在非加权图上而已。我们考虑这样一个变化版本：在草原上，骑士必须沿着管道走，国王可以走捷径。骑士和国王分布在若干个据点内，现在要集中起来开会，国王可以在某个据点上骑士的马，这样，之后计算距离就不计国王了。那么，给定据点分布和道路图，问，在哪个据点开会代价最小？

/*
ID: blackco3
TASK: camelot
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
const int _max_row_(26), _max_col_(30);
int n_row, n_col, n_knight ;
struct t_chess {
	int row, col ;
} king , knights[_max_row_*_max_col_] ;
int min_dis[_max_row_][_max_col_][_max_row_][_max_col_] ;

int drow[8]={2, 2, -2, -2, 1, 1, -1, -1 } ;
int dcol[8]={1, -1, 1, -1, 2, -2, 2, -2 } ;
int dis[_max_row_][_max_col_] ;
t_chess queue[_max_row_*_max_col_] ;
void get_min_dis(int crow, int ccol){
	memset( dis, 0xff, sizeof(dis) );
	t_chess *head=queue, *tail=queue ;
	tail->row=crow, tail->col=ccol, tail++, dis[crow][ccol]=0 ;
	register int hrow, hcol, ndis, nrow, ncol, dir ;
	do{
		hrow=head->row, hcol=head->col, ndis=dis[hrow][hcol]+1, head++ ;
		for( dir=0; dir<8; dir++ ){
			nrow = hrow + drow[dir], ncol = hcol + dcol[dir] ;
			if( nrow<0 || nrow>=n_row || ncol<0 || ncol>=n_col || dis[nrow][ncol]!=-1 )
				continue ;
			tail->row=nrow, tail->col=ncol, tail++, dis[nrow][ncol] = ndis ;
		}
	} while ( head != tail ) ;
	for( int ir=0; ir<n_row; ir++ )
		for( int ic=0; ic<n_col; ic++ )
			min_dis[crow][ccol][ir][ic] = dis[ir][ic] ;
}

int help_knight[_max_row_][_max_col_], king_dis[_max_row_][_max_col_] ;
inline void get_king_help( int crow, int ccol ) {
	int row_dis = king.row > crow ? king.row - crow : crow - king.row ;
	int col_dis = king.col > ccol ? king.col - ccol : ccol - king.col ;
	king_dis[crow][ccol] = row_dis < col_dis ? col_dis : row_dis ;	
}

int get_cost( int crow, int ccol ) {
	int total = 0 ;
	for( int i=0; i<n_knight; i++ ){
		int cur=min_dis[knights[i].row][knights[i].col][crow][ccol] ;
		if( cur==-1 )
			return -1 ;
		total += cur ;
	}
	int king_cost = king_dis[crow][ccol] ;
	for( int ir=max(0,king.row-2); ir<min(n_row,king.row+3); ir++ )
		for( int ic=max(0,king.col-2); ic<min(n_col,king.col+3); ic++ ){
			if( min_dis[ir][ic][crow][ccol]==-1 )
				continue ;
			int help_dis=0x7fffffff ;
			for( int who=0; who<n_knight; who++ ){
				int kr=knights[who].row, kc=knights[who].col ;
				if( min_dis[kr][kc][ir][ic]==-1 || min_dis[kr][kc][crow][ccol]==-1 )
					continue ;
				int cur_cost = min_dis[ir][ic][crow][ccol] + min_dis[kr][kc][ir][ic] +
			                 king_dis[ir][ic] - min_dis[kr][kc][crow][ccol] ;			
				if( cur_cost < king_cost )
					king_cost = cur_cost ; 
			}
		}
	return total+king_cost ;
}

int main() {
	freopen("camelot.in", "r", stdin);
	freopen("camelot.out", "w", stdout);
	char row_char ;
	cin >> n_col >> n_row >> row_char >> king.col ;
	king.row = row_char - 'A' , --king.col ;
	for( n_knight=0; cin >> row_char >> knights[n_knight].col ; n_knight++ ) 
		knights[n_knight].row = row_char -'A' , --knights[n_knight].col;

	for( int ir=0; ir<n_row; ir++ )
		for( int ic=0; ic<n_col; ic++ )
			get_min_dis( ir, ic );	

	for( int ir=0; ir<n_row; ir++ )
		for( int ic=0; ic<n_col; ic++ )
			get_king_help( ir, ic );

	int min_cost = 0x7fffffff ;
	for( int ir=0; ir<n_row; ir++ ){
		for( int ic=0; ic<n_col; ic++ ){
			int ccost = get_cost( ir, ic ) ;
			if( ccost != -1 )
				min_cost = ccost<min_cost ? ccost : min_cost ;
		}
	}
	cout << min_cost << endl ;
	return 0 ;
}