USACO/camelot

来自NOCOW

由于广告问题，编辑本页时请在摘要的开头写上“asd::”（红字部分），谢谢合作。 --Cosechy 14:17 2010年2月11日 (CST)

[编辑] 官方题解

这是对最短路算法的修改。如果没有王，最短路算法就可以解决每个骑士到每个格子须走的距离。这样，集中到一个格子的费用就是将所有骑士到此格的距离简单累和，这是很好算的。

对于王，考虑一个骑士在某格接起王再走到集合点。这比简单地走到集合点要多花几步。考虑骑士为接王多走的几步（接王的花费）。修改最短路算法，在原状态上加一个布尔标志以表明其实是否带着王。

在这里，在某一位置集合的费用就是每个骑士到达此处所需步数之和加上接王的最小花费。因此，对每个格子，我们维护两个值，当前所有骑士集中到此格的距离和（集合值）以及由某骑士路上接王的最小花费（注意“接王”的一种方式是王自己走到集合点）。然后，当我们得到一个新骑士，我们跑一下最短路算法，添加他到每格的花费（不接王）。并且，对每个格子检查此新骑士是否能用比之前骑士更少的步数接王，如果能，更新那个值。

处理完所有骑士之后，我们将所有格子的集合值与接王费用相加以求得最小值。（翻译首秀，请多指教） ——By 小刘

（C语言的的第一个例程应是官方例程，进一步理解此官方算法可参考此程序）

我的思路和官方的一样，我用的是两次bfs，对于每一个knight，第一次bfs用knight遍历整个棋盘，结果与前面的结果相加;第二次枚举汇合点，如果这个汇合点可以改进其他点的步数，则入队，开始bfs。 --by define14

同意楼上，就是用SPFA算法求各骑士带着王到某个点的最短路程。用dist[pf][pt]表示从pf点到pt点骑士所需的最短路（用bfs即可），dist2[pf][pt]则表示如果某骑士从pf点出发，与王共同到达pt所需的最短路。设骑士在px点捎上王，则dist2[pf][pt]=dist2[pf][px]+dist[px][pt]，这样就可以用SPFA做了。最慢的数据也只需要0.400秒。 ——MK

[编辑] 分析

　　本题就是一个求所有点对间的最短路然后处理的问题。最短路好求，难点在于有王，王可以自己一格一格地走到汇集点；也可以让某个骑士先跳到他所在的格子，再一起到汇集点；也可以先走几步，再让骑士跳到他所在的格子，再一起到汇集点。
　　d[i,j,x,y]表示点(i,j)到(x,y)的最短路长，可以用BFS求出。王的坐标为(kx,ky)，最终结果用ans储存。基本思路是枚举一每个格子作为所有骑士的汇集点(i,j)，再枚举每个格子，以这个格子为王和某个骑士的相遇处(x,y)，再枚举每个骑士坐标(m,n)。求出d[i,j,x,y]+d[x,y,m,n]+max(abs(kx-x),abs(ky-y))-d[i,j,m,n]的最小值，将汇集点到所有骑士的最短路和s加上这个值，与ans比较取小者。
　　枚举的时间复杂度为O(n^3)，超时不是一般地严重……于是开始优化。最优化剪枝是必要的，当某个汇集点到所有骑士的最短路s已经大与了ans时直接退出。尽管效率大大提高，但仍然严重超时。于是想一想，王和骑士的相遇点可能出现在哪些位置上？显然王走的比骑士要慢，那么应该尽量要让王少走，所以王需要先走的情况只可能是骑士无法到达的地方或者骑士到达需要绕一圈的情况。可以构想一下骑士在王附近时达到王的路径，就不难发现，相遇点只应该在王的附近很短的距离以内。估算一下，相遇点就在王的坐标加减2的范围内枚举就可以了，经过证明，这样做是正确的（好象有人已经在OIBH上发表了证明方法）。
　　加上这两个优化，就可以比较快地AC了。

[编辑] 证明

只需要考虑国王坐标范围+-1即可，下面给出不太严格的证明（我称为伪证明）：

性质1：假设国王和骑士在超过国王座标点一步范围外集合，集合点称为“原汇合点”，那么，当骑士由原汇合点向国王迈进一步，则总汇合步数减少一步。

性质2：可以保证这样做得到的解不大于在原汇合点汇合得到的解。因为“当骑士由原汇合点向国王迈进一步，则总汇合步数减少一步。”

意味着，骑士原路返回“原汇合点”的话，总汇合步数和原来相同。

[编辑] 我来说几句

要考虑国王坐标范围+-2。

如最后一个数据：

8 8
G 4
E 4 D 6

comment: 你说错了！骑士如果去带王必须+-1，但这个点骑士没有带王！USACO官方讲的很清楚！

如果数据强一点,+-2都不行,恐怕得改个+-5或者更大+-1这个规则不是被证明过的了么？！望高手说明为什么不行。 ——by mamsds

只需要考虑国王的+-1范围作为骑士接王的地点。但是，需要额外考虑不带王的情况，即king直接自己走到最终集合点。

给个范例

* 表示王，O表示骑士 —表示空格
* - - - - -
- - - - - -
- - - - - -
- - - O - -
- - - - - O

在（4，4)点回合，只要四步而这个最优解不在正负3之内啊

comment by ftfish

深搜也可以

谁说只准宽搜来着？我深搜照样过，但需要控制一定的搜索层数（否则虽然答案正确，但也会TLE）。

详情请见：pascal代码 --sxpeter

枚举王+-2范围的反例

最优解是6

最短路一样

最短路都用d数组存储，难道不用考虑骑士与王走法的差别吗?

好像不用想那么多

预处理任意两点间骑士所需步数，枚举集合点，枚举接王的骑士，枚举接王的点。加最优性剪枝。两个点上1s，最慢1.4s，过了。

忠告一枚

千万别像咱一样把横纵坐标读反了，结果debug一个下午。

另外，加了第一个剪枝，暴力枚举接王的点是可以AC的，最慢的点1.058s。 - yzyzsun

[编辑] 新解（错误）

首先汇合点不一定在+-1之内，也同样不在234...之内。

证明：上面的伪证明的思路是对的但是证反了，骑士绕远路迈进一步，王并不一定减2步，而有可能只-1，比如田字格。

所以骑士原路返回的话，新汇合步数>=原来的步数。如果还有疑问，请看这个例子：

k代表王，1代表骑士，0代表空格。

  a b c d e f g h i j k l m n o p q r s t u v w x y z
1 k 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0

这个例子卡掉了所有的C++例程和C的第二个例程。这个例子的集合点在P 16(16,16)，只需31步，而我们大部分例程都输出33+，有一个输出28的= =，可能是没加返回的路程吧。至于C的第一个例程，好像是把所有骑士在所有点接王的差价算出来了，效率比较高，过了。

(这个地方提出质疑，因为我试过，如果集合点在（P，16）最少34步，方法如）

骑士 1：N12->L11->J10->H9->F8->D7->C5->B3->A1(接国王)->B3->C5->D7->F8->H9->J10->L11->N12->O14->P16 总共走了18步（可以有其他路径，不可能更短）

骑士 2：O18->P16 共走了1步（不可能更短）

骑士 3：P16 原地不动，走了0步（不可能更短）

骑士 4：P20->O18->P16 共走了2步（可以有其他路径，不可能更短）

骑士 5：Q18->P16 共走了1步（不可能更短）

骑士 6：R15->P16 共走了1步（不可能更短）

骑士 7：R17->P16 共走了1步（不可能更短）

骑士 8：R20->Q18->P16 共走了2步（可以有其他路径，不可能更短）

骑士 9：S19->R17->P16 共走了2步（可以有其他路径，不可能更短）

骑士10：T14->R15->P16 共走了2步（可以有其他路径，不可能更短）

骑士11：T16->R15->P16 共走了2步（可以有其他路径，不可能更短）

骑士12：T18->R17->P16 共走了2步（可以有其他路径，不可能更短）

一共走了18+1+0+2+1+1+1+2+2+2+2+2=34步

这样我们就有了一个新思路，只移动王，而不让骑士走多余的步数。在对每一个点进行BFS的时候，我们记录所有骑士的最短路中经过的所有点，这样王可以移动到离自己最近的一个骑士已经过的点。对于每个点记录back数组，一旦宽搜到此点时，如果是最短距离就把back设置成来源点。来源点不一定是一个，所以我开了个8个的数组。一旦搜到一个有骑士的点且是最少步数，那么延back数组把所有经过的点设成可以由骑士在不绕远的情况下到达。这样最后找一下离王最近的可到点距离是多少就好了（我还写得BFS= =）。效率MNlog(MN)，调用MN次，(MN)^2log(MN)，可能常数偏大，最慢的点0.3+。

（见代码by luanshaotong）

事实上，luanshaotong 的算法是错误的---这缘于其假设“不应让骑士走多余的路程”。现给出一个反例来证否这一点：

8 10
A 8
H 7
I 1
J 2
J 4

根据 luanshaotong 的算法，其程序输出了 11 作为最小距离和；正确的答案则应是10。

    A B C D E F G H I J
(1) 0 0 0 0 0 0 0 0 x 0
(2) 0 0 0 0 0 0 0 0 0 x
(3) 0 0 0 0 0 0 0 4 0 0
(4) 0 0 0 0 0 3 0 0 0 x
(5) 0 0 0 2 0 0 0 0 0 0
(6) 0 0 0 0 0 1 0 0 0 0
(7) 0 0 0 0 0 0 0 x 0 0
(8) * 0 0 0 0 0 0 0 0 0

如上表，"4"是所有棋子应当集合的格子，"*"代表国王，"x"代表骑士，"1"至"4"表示骑士 H7 应当走的（正确）路径。

在枚举集合点直至考虑"4"时，luanshaotong 的算法首先求出所有骑士到达"4"的最短路径。在这些路径上的顶点中，G5 是使国王由 A8 行至的所需步数最少（6步）的顶点。因此接下来，算法选择骑士 H7 在 G5 接应国王。其余骑士（I1, J2, J4）则直接行至"4"。这样，该算法总共需要 11 步来会合所有棋子。

然而，正确的方案是使骑士 H7 在"2"处接应国王（注意骑士 H7 走了多余路程），其余骑士（I1, J2, J4）直接行至"4"。这样共需 10 步。

因此，luanshaotong 的算法不正确。

by SillyRobot

我用了迭代逼近法过了全部数据（最慢0.1s），觉得上面说得有点麻烦了，特别是那个求back，实在太麻烦了

枚举所有棋子的集中点（可加优化）

枚举 king-picked knight

下面迭代逼近，从king所在地向八个方向搜索（最开始逼近的幅度是r/2,c/2，直到幅度等于零，复杂度log(n)）

考虑到日走形的特殊性（隔一个格可能多产生3,4步数）所以在迭代逼近时枚举此点的九宫（利用+-的证明可得），找出最小的即可

这个移动king的思路我一开始也有，后来发现有时骑士不走最短路径而稍稍绕路去带king，会得到更优的结果。反例如下，1表示骑士，k表示王，在（g，5）会合，m表示骑士（a，4）的最短路径，s表示该骑士的另一种更优的走法

  a b c d e f g h i
1 0 0 0 0 0 0 1 0 1
2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 1 0
4 1 0 0 0 0 0 0 0 1
5 0 0 m 0 0 0 1 0 0
6 0 s 0 0 m 0 0 0 0
7 0 0 0 0 0 s 0 0 0
8 0 0 s 0 0 0 0 0 0
9 0 0 0 0 s 0 0 0 0
100 0 0 0 k 0 0 0 0

骑士（a，4）选择路线s的话，到会合点要5步，但王只要一步就能被骑士带上，而路线m，骑士可以3步到达，但王则最少要走4步。

[编辑] 枚举+-1的反例（官方新增的第20个数据）

8 8
D 5
B 1
F 1
B 3

最优解是5，而不是6

汇合点在(D,2)

[编辑] 一个万无一失的方法

对于骑士带王去会合的情况，枚举王的原位置和八个方向，也就是说王和骑士的汇合点相对于王的原位置为上下左右或者斜45度方向。

比如在8*8的棋盘上，王的位置用k表示，需要枚举的带王的点用1表示，其余点用0表示则有下图：

0 0 1 0 0 1 0 0
1 0 1 0 1 0 0 0
0 1 1 1 0 0 0 0
1 1 k 1 1 1 1 1
0 1 1 1 0 0 0 0
1 0 1 0 1 0 0 0
0 0 1 0 0 1 0 0
0 0 1 0 0 0 1 0

对于其他带王点的情况，总可以等效为以上情况之一,这样枚举不会超时。参见C++参考代码，ID:huilong1

看了半天楼上还是算法最简单。

[编辑] 另一种解法 DP

自己看代码【名字：zlk87902【因为太难解释= =！你这个东西根本看不懂

[编辑] 参考代码

C
C++
Pascal
Java

[编辑] 引用

[1]

[编辑] 注意

此页内容之前被广告覆盖，现已恢复，请不要张贴广告影响OIer们的正常学习工作秩序。

也希望OIer看到此类现象后及时修正。谢谢！ ——By JackDavid127