USACO 2020 Dec Gold

1. 「USACO 2020 Dec Gold」Replication 复制

本题相当于机器人在行进的过程中，其体型会不断扩大。当 ”一块“ 机器人某个位置接触到岩石以后，停止前进。

下文中，我们把原来的机器人叫做 本体，复制出来的机器人叫做 复制。

.....    .....    ..X..
.....    ..X..    .XXX.
..X.. -> .XXX. -> XXXXX
.....    ..X..    .XXX.
.....    .....    ..X..

上图是一个机器人复制两次后，得到的机器人群，可以看到，进过 $i$ 次复制以后，所有与本体距离不超过 $i$ 的网格，都会有机器人存在。这些位置，有可能是本体经过的位置，也可能是复制经过的位置。

预处理 rock_dist 数组

rock_dist 数组保存每个网格与最近岩石的距离。该数组可以从所有的岩石出发，执行多源 BFS 求得。

有本体经过的位置

因此，我们首先处理有本体经过的位置。本体能否进入某个位置 $(r, c)$，这取决于本体复制的次数 $t$，以及离最近岩石的距离 $rockDist[r][c]$。

具体来说，假设本体当前的位置为 $(r_1, c_1)$，准备移到 $(r_2, c_2)$。

从出发点到当前位置的距离为 $dis_1$，那么所需的时间也为 $dis_1$。根据题意，我们在本体准备移动的时候，检查其是否会进行复制，若要进行复制，且会与岩石相撞，则不能继续移动。记复制的次数 $t = \displaystyle \lfloor \frac {dis_1}D \rfloor$。若 $t \ge rockDist[r][c]$。则本体不能继续移动。该式等价于 $dis_1 \ge D \times rockDist[r][c]$。

接下来，我们检查能否移至 $(r_2, c_2)$。记花费的时间为 $dis_2$。若 $\displaystyle \lfloor \frac {dis_2 - 1}D \rfloor \ge rockDist[r][c]$，则不能移至 $(r_2, c_2)$。注意为什么是 $dis_2 - 1$ 呢？因为复制发生在移动之后，故我们计算通过 $\displaystyle \lfloor \frac {dis_2 - 1}D \rfloor$ 来计算复制次数。式子等价于 $dis_2 > D \times rockDist[r][c]$。

复制经过的位置

若一个本体在某个网格的 rockDist 值为 $r$，那么我们可以在该格子停留，直到机器人群总共复制了 r - 1 次。因此，与其距离小于 $r$ 的网格，都可以有机器人存在。（题目说的是每次朝四个方向移动，我们可以来回移动，那么，在 r - 1 的范围内，要么是复制，要么是本体）。

因此，我们按照本体经过的位置按 rock_dist 值进行分类，从大到小进行一种变形的 BFS，就可以得到所有可能的网格，具体实现参考代码。