ACWing1386 卡米洛特
题目描述
题目链接：1386. 卡米洛特 - AcWing题库。
几个世纪之前，亚瑟王每年元旦都会和圆桌骑士们一起聚会。
为了纪念这些事件，我们考虑一个棋盘游戏，在一个 R×CR×C 的方格棋盘中，放着一个国王和若干个骑士。
没有任何两个骑士被放到同一个方格中。
一个 8×8的棋盘如下所示：
国王可以移动到任何一个相邻的方格中，前提是不能走出棋盘：
骑士可以从下图黑子位置跳到任一白子位置，前提是不能走出棋盘：
在游戏过程中，玩家可以在同一方格中放置多个棋子。（假设方格够大，任何棋子都不会影响到其他棋子的自由移动。）
玩家的任务是移动这些棋子，将它们移动到同一个方格之中，并且使得移动步数尽可能少。
棋子的移动需要遵守之前叙述的移动规则。
另外，当国王和一个或更多骑士处于同一方格中时，玩家可以选择让国王和其中一个骑士从这个位置开始一起行动直至任务完成。
此时两者视为一个整体，按照骑士的移动规则移动，并且每次移动只算一步。
请输出将所有棋子汇聚在一个格子之中，至少要移动多少步。
汇聚在任何一个格子上均可。
输入格式
第一行包含两个整数 RR 和 CC，表示棋盘的行数和列数。
接下来若干行，用来描述国王和骑士在棋盘中的位置。
每行包含一个或多个字母/数字对，第一对描述的是国王的位置，其他对描述的是骑士的位置，棋盘中可能没有骑士，也可能所有方格中都有骑士。
行从 11 开始编号，列从 AA 开始编号。
输出格式
输出一个整数，表示最少移动步数。
数据范围
1≤R≤30 1≤C≤26
输入样例：
输出样例：
样例解释
8×8的棋盘上，国王在 D4，四个骑士分别在 A3,A8,H1,H8
四个骑士的行动为：
骑士一：A3−B5 （一步）
骑士二：A8−C7−B5（两步）
骑士三：H1−G3−F5−D4(带上国王)−B5(四步)
骑士四：H8−F7−D6−B5（三步）
所有棋子汇集在 B5，共移动 10 步。
算法思路
说实话，这个题上来直接把我整懵了，这是要干啥？但是不要被吓到，这个题仔细分析一下就可以发现实际上是求一个点，使得所有棋子到这个点的距离最小。如果不考虑国王的存在，那问题就会简化很多。
任意给定一个点，求某一个骑士到这个点耗费的最小步数是可求得的。那么只要我们把每一个棋子到每一个点的最小步数求出来，比如存放在$dist[k][i][j]$中，k是骑士的编号，i是目的格子的行号，j是目的格子的列号。然后求出$distance[i][j]={\sum_{k=0}{dist[k][i][j]}}$。然后比较distance数组哪个最小即可。求骑士到任意一点的距离实际上就是单源最短路径了，只不过点一共有CR个，每个位置邻接的点就是按“日”字走法可达的位置，节点之间的耗费权值是1。常用的单源最短路径方法有：dijkstra算法、bellman-ford算法、spfa算法，我这里就采用使用了队列的spfa算法了。
如果只考虑骑士不考虑国王的话，这个问题算是已经解决了，但可惜的是这个问题不能忽略国王。那么我们现在的任务是求出国王到某一点i,j的最短距离。现在需要考虑的是，上面求得的到某一点的最短距离中，骑士的路径可能经过国王，也可能不经过国王，如果经过国王就好办了，直接采用上面的结果就可以了，麻烦的是如果不经过国王。如果不经过国王的话，国王要走到这一位置有三种情况：国王自己一步一步走过去、走到离自己最近的骑士经过的点和骑士一起过去、专门令一个骑士来接自己。一般情况下后面两种情况会是最优解，但是也有第一种情况是最优解的特殊情况。为了增加专门让一个其实来接自己的特殊情况，我们可以用两个数组分别来保存骑士到某一个顶点接国王/不接国王需要的距离。我们可以先把国王到达某一点(i,j)的最小距离初始化为$king[i][j]$，那么
注意这里要遍历所有的骑士,这一步可以在每次使用spfa算法时进行一次，最后正好可以求出来。
king[i][j]=Math.min(king[i][j],骑士接国王到(i,j)的距离−骑士不接国王到(i,j)的距离)。
如果上面的函数值取到了$骑士接国王到(i,j)的距离-骑士不接国王到(i,j)的距离)$,说明这是骑士为了接国王额外的路径耗费，因为国王被接走了，所以国王的耗费＝0，此时$king[i][j]$就可以“代表”国王走到这一点的最小耗费。
实现代码
Last updated