USACO Section3.3 Camelot 解题报告

DONG Yuxuan @ Jul 28, 2015 CST

网上充满了对这个问题的错误解法,我想我需要给出一个正确的解法,并解释为什么网上常见的解法是错误的。

问题描述

一个 $R$ 行 $C$ 列的棋盘($R \leq 30, C \leq 26$),上面有一个国王与若干骑士,其中国王的行走规则如下:

king-rule

骑士的行走规则如下:

knight-rule

同一个方格里可以放任意多个棋子(包括国王与骑士),并且我们假定每个方格都足够大,使得任意一颗棋子都不会阻挡另外棋子的移动,除此之外,如果国王与某一个或多个骑士在同一个方格里相遇,那么国王可以选择一位骑士背着他走(既跟随这个骑士一起按照骑士规则移动)。

假定最开始的时候没有两个骑士在同一个方格里,问最少需要多少步才能把所有骑士与国王移动到同一个方格里。

分析

我们称国王与骑士们最终汇聚的方格为聚集点,现假定聚集点已经确定了,我们来考虑如何用最少的步数将所有棋子移动到聚集点。首先国王靠自己走到任何一个格子的最短路径长度是容易计算的:max(dx,dy),其中 dx, dy 分别是行差与列差,接着我们记 d[x][y] 表示一个骑士从聚集点走到格子(x,y)的最短路径长度,可以通过一次 BFS 在 $O(N)$ 时间内计算出所有的d[x][y]($N=RC$)。

考察一个初始位置在(x,y)​的骑士,他要么按照自己的走法一路走到聚集点,这代价(步数)是d[x][y];要么他先走到某一点,国王也走到这同一点,他载起国王,再从这点出发走向聚集点,载起国王的这一点我们称为接客点(x',y'),这样做的代价是骑士走到(x',y')的代价,加上国王走到(x',y')的代价,再加上d[x'][y'],显然随着接客点的不同,这代价也是不同的,我们取这些代价中的最小值,记为d'[x][y],也就是说d'[x][y]代表一个在(x,y)的骑士,先到某一点接起国王(国王也需要走到这一点)并载至聚集点所需的最小代价。

如果我们有某种方法能够以足够快的速度计算出所有的d'[x][y],那么我们便能用如下的算法求解问题:

//将国王自己走到(x,y)的最短路径长度记为king(x,y)

mincost = infinity
对于棋盘上每一个点(r,c):
	将(r,c)作为聚集点
	BFS计算棋盘上每个点 (x,y) 对应的 d[x][y]
	计算棋盘上每个点 (x,y) 对应的 d'[x][y]
	s = 每个骑士所在点的 d[x][y] 之和 + king(r,c)
	对于每一个骑士的位置 (x,y):
		s = min(s, s - king(r, c) - d[x][y] + d'[x][y])
	mincost = min(s, mincost)

mincost 即为所求

现在唯一的问题便是如何计算d'[x][y],这可以使用 Dijkstra 算法来做,因为对于一个在(x,y)的骑士来说,他的最短路径只有两种情况,要不然就骑士原地不动,等待国王走到(x,y),然后载起国王走到聚集点,要不然他先随便走一步到他的某个邻接点(x',y'),则问题化归为求解d'[x'][y'],形式化地说:

d'[x][y] = min{ king(x, y) + d[x][y], 1 + d'[x'][y'] | (x',y')是(x,y)的邻接点(按骑士走法)}

我们可以看出这个方程与经典最短路径之间有着千丝万缕的联系,其唯一区别在于对于每一个点,我们除了考虑其从某邻接点走过来的情况之外,还要考虑一个特殊的情况,既king(x,y) + d[x][y],然而我们可以通过在图中添加一个虚构的顶点s,它到其他每一个点(x,y)的边权为king(x,y) + d[x][y],这样一来从s出发的单源最短路径,便是上面那方程的解,利用优先队列优化的 Dijkstra 算法,我们可以在 $O(NlogN)$ 内计算出这个解。再结合上面的总的算法框架,原问题可在 $O(N^2logN)$ 内求解。

关于一种常见的错误解法

Camelot 这道题,咱们在搜索引擎里搜搜就能发现网上流传着一类 $O(N^2)$ 的解法,这类解法能够过掉 USACO 的所有测试数据,然而它是错的

这类算法主要是基于下面这个观察:

骑士走得快,国王走得慢,所以在骑士接国王的过程中,国王要尽量少走,让骑士多走。

所以我们认为接客点必然是在国王的周围,也就是存在一个常数M,使得最优的走法一定是在国王的M步之内去接国王,这样我们便可以枚举聚集点,对于每个聚集点再枚举由哪个骑士去接国王,对每个确定的骑士,再枚举接国王的位置,由于接国王的位置只有常数多个,所以这算法是 $O(N^2)$ 的。

然而事实上,我们可以构造必须在M圈之外去接国王的情况:

-------@
-----+--
--------
--------
--*-----
--------
--------

这是 $M=2$ 的例子,其中*表示国王,+表示骑士,@表示聚集点,在这个例子中,最优的走法是国王直接走到骑士的格子,然后骑士再载着国王一步走到聚集点,一共需要4步,而如果要在2圈之内去接国王,不管怎么样都至少需要5步才能送到聚集点。

这种模式可以扩展到 $M>2$ 的情况,我们只需要把骑士放在以国王为中心的 $M$ 圈形成的矩形的对角上,然后让聚集点是沿着这个对角方向,骑士一步可达的格子即可。