自动搬运

查看原文

来自洛谷，原作者为

	璀璨星空1 倘若我们义无反顾去做不可能之事，世上便再没有不可能。

搬运于2025-08-24 22:50:02，当前版本为作者最后更新于2023-09-09 06:13:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

如溪水潺潺淌过古街　带走了如梦般的时节
小桥上人潮络绎不绝　牵引我思绪层出不迭

我们的程序将分两个阶段进行。在第一阶段中，我们从 $(0,0)$ 出发走到 $(n-1,m-1)$，找到并标明一条从 $(0,0)$ 到 $(n-1,m-1)$ 的最短路；在第二阶段中，我们从 $(n-1,m-1)$ 出发走回 $(0,0)$，在回溯的过程中将所有不在最短路上的格子的标记清零。

第一阶段：标明一条从 $(0,0)$ 到 $(n-1,m-1)$ 的最短路。

我们先思考 $\text{subtask 3}$，即一棵树的情形。我们从 $(0,0)$ 开始 DFS。设当前 DFS 到 $(x,y)$，我们需要枚举 $4$ 个方向，并依次扩展那些 $=0$ 并且不同于来时的路的方向。我们有两种选择：

• 用一个 $(x,y)$ 的颜色 $c(x,y)$ 记录当前扩展到了哪个方向，每次访问到 $(x,y)$ 就将 $c(x,y)$ 增加 $1$；
• 每当 DFS 完一个 $(x,y)$ 没找到通向 $(n-1,m-1)$ 的路，就将 $c(x,y)$ 改成 $2$，表示将 $(x,y)$ 这个格子堵住。

可以看出，采用第一种选择将大大增加所用的颜色个数。所以我们倾向于采用第二种选择。在 $\text{subtask }4,5$ 中我们继续沿用第二种选择：当 DFS 完 $(x,y)$ 的某个儿子 $(x',y')$ 时，就将 $c(x',y')$ 改成某种特殊的标记，表示以 $(x',y')$ 为根的 DFS 已经结束。

再思考 $\text{subtask 4}$。$\text{subtask 4}$ 保证了最短路 $=n+m-2$，也就是说我们只会向右走或向下走。相比于 $\text{subtask 5}$，$\text{subtask }3,4$ 的简单之处在于我们只需要找到某一条从 $(0,0)$ 到 $(n-1,m-1)$ 的路径，这条路径便自然是最短路。

如果采用第二种选择的话，我们沿用 $\text{subtask 3}$ 的 DFS 就可以直接解决 $\text{subtask 4}$。可以获得 $35$ 分。

有了 $\text{subtask }3,4$ 的提示，我们再来思考 $\text{subtask 5}$。要求从 $(0,0)$ 到 $(n-1,m-1)$ 的路径最短，我们非常希望 BFS 而不是 DFS。但是由于 Pulibot 的视角是局部的，它天然更适合 DFS 而不是 BFS。

所以我们采用类似迭代加深的办法。我们一轮一轮扩展，在第 $i$ 轮标记所有 $\text{dis}(x,y)=i$ 的 $(x,y)$。我们会遇到一个重要的问题：

• 在第 $i$ 轮开始的时候，与 $=0$ 的 $(x',y')$ 接触的 $(x,y)$ 一定是 $\text{dis}=i-1$ 的。但是给 $(x',y')$ 做了标记以后，$(x',y')$ 这个格子就与外界接触了。怎么防止 $\text{dis}=i$ 的 $(x',y')$ 继续扩展下去，导致 $\text{dis}\geq i+1$ 的格子在第 $i$ 轮就被标记呢？

考虑 BFS 树。我们每次扩展一层叶子。我们用 $4$ 个方向 $\leftarrow,\downarrow,\rightarrow,\uparrow$ 记录一个 $(x,y)$ 在 BFS 树上的父亲，在遍历 BFS 树的时候，我们只能沿着父亲到儿子的方向走。这样我们便不可能沿不同的路径多次访问到同一个 $(x,y)$。再加上 $0,1,2$ 这 $3$ 种颜色，总共是 $7$ 种标记：

若不识梁祝变成蝴蝶　驾紫烟穿过天上宫阙
绝不知人间多愁离别　吹落叶散作秋风清切

现在我们设计 DFS 的具体流程。在第 $i$ 轮，我们沿着 BFS 树的第 $0$ 到 $i-1$ 层进行 DFS，扩展出它的第 $i$ 层。设当前 DFS 到了 $(x,y)$，那么从 $(0,0)$ 到 $(x,y)$ 路径上的所有格子都 $=2$。$(x,y)$ 的 $4$ 个邻居中一定有一个 $=2$，那是 $(x,y)$ 的父亲 $\text{Fa}(x,y)$。

如果 $(x,y)$ 的其他 $3$ 个邻居中有指向 $(x,y)$ 的箭头，则说明 $(x,y)$ 不是叶子。我们按西、南、东、北的顺序找到第一个指向 $(x,y)$ 的 $(x',y')$，走到 $(x',y')$，然后将 $c(x',y')$ 改成 $2$，从 $(x',y')$ 出发继续 DFS。

如果 $(x,y)$ 的其他 $3$ 个邻居中没有指向 $(x,y)$ 的箭头，则说明 $(x,y)$ 是叶子。我们需要将 $(x,y)$ 所有 $=0$ 的邻居 $(x',y')$ 指向 $(x,y)$，然后立刻回溯。我们先将 $c(x,y)$ 改成 $1$。当 Pulibot 站在一个 $1$ 上时，它会按西、南、东、北的顺序找到第一个 $=0$ 的 $(x',y')$，走到 $(x',y')$，然后将 $(x',y')$ 指向 $(x,y)$ 并走回 $(x,y)$；如果 $4$ 个邻居中已经没有 $0$ 了，说明 $(x,y)$ 的子树已经扩展完了，我们将 $c(x,y)$ 改成 $0$，并返回 $\text{Fa}(x,y)$，标示从 $\text{Fa}(x,y)$ 到 $(x,y)$ 这条路已经扩展完了。

当 $(x,y)$ 的子树扩展完了的时候，我们选择将 $c(x,y)$ 改成 $0$ 作为特殊的标记。这样做是很方便的：当 $\text{Fa}(x,y)$ 的儿子都扩展完了之后，$\text{Fa}(x,y)$ 的周围一圈都是 $0$，然后 $\text{Fa}(x,y)$ 就会变成 $1$ 并且将周围的 $0$ 都重新指回 $\text{Fa}(x,y)$，最后 $c\big(\text{Fa}(x,y)\big)$ 再从 $1$ 变成 $0$。

最后当 $c(0,0)=1$ 并且 $(0,0)$ 的 $4$ 个邻居都 $\neq0$ 的时候，就意味着第 $i$ 轮已经结束了。我们将 $c(0,0)$ 改成 $2$，从此开启第 $i+1$ 轮。

整理前述的所有东西，我们得到了一个初步的做法：

• 如果 $c(x,y)=0$：
  • 如果 $(x,y)=(0,0)$，则将 $c(x,y)$ 改成 $1$ 并停在原地；
  • 否则检查 $(x,y)$ 的 $4$ 个邻居。若邻居中有 $1$，则按西、南、东、北的顺序找到第一个 $1$，将 $(x,y)$ 指向那个 $1$ 并走过去。
• 如果 $c(x,y)=1$：
  • 检查 $(x,y)$ 的 $4$ 个邻居。若邻居中有 $0$，则按西、南、东、北的顺序找到第一个 $0$，直接走过去；
  • 否则如果 $(x,y)=(0,0)$，则将 $c(x,y)$ 改成 $2$ 并停在原地；
  • 否则检查 $(x,y)$ 的 $4$ 个邻居。若邻居中有 $2$，则按西、南、东、北的顺序找到第一个 $2$，将 $c(x,y)$ 改成 $0$ 并走过去。
• 如果 $c(x,y)=2$：
  • 检查 $(x,y)$ 的 $4$ 个邻居。若邻居中有指向 $(x,y)$ 的 $(x',y')$，则按西、南、东、北的顺序找到第一个 $(x',y')$，直接走过去；
  • 否则将 $c(x,y)$ 改成 $1$ 并停在原地。
• 如果 $c(x,y)\in[3,6]$，则将 $c(x,y)$ 改成 $2$ 并停在原地。

最后，我们将会到达下图所示的局面。直接沿着标明的最短路返回并将路径上的 $2$ 都改成 $1$，可以获得 $71$ 分。

第二阶段：回溯清理所有不在最短路上的格子的标记。

最后我们再考虑回溯清理的问题。当 Pulibot 走到了 $(n-1,m-1)$ 并且 $c(n-1,m-1)\in[3,6]$ 时，意味着已经找到并标明了一条从 $(0,0)$ 到 $(n-1,m-1)$ 的最短路，应该开始回溯清理了。我们的目标是到达下图所示的局面：

我们要干的事是将一棵树删空。当我们访问到一个结点 $u$ 的时候，我们先依次访问 $u$ 的所有儿子 $v_i$ 并将 $v_i$ 的子树删空，然后再删掉 $u$ 并回到 $\text{Fa}(u)$，继续删除 $\text{Fa}(u)$ 其他儿子的子树。用 $\text{2D grid}$ 的语言，我们从 $(n-1,m-1)$ 倒着走回 $(0,0)$，将一路上所有的 $2$ 改成 $1$。当一个 $(x,y)$ 被从 $2$ 改成 $1$ 时，我们开始清理 $(x,y)$ 的子树。当 Pulibot 站在一个 $1$ 或者一个箭头上时，如果 $(x,y)$ 的儿子已经都变成了 $0$，那么就将 $(x,y)$ 也改成 $0$ 并走回 $\text{Fa}(x,y)$；如果 $(x,y)$ 的儿子中还有指向 $(x,y)$ 的箭头 $(x',y')$，那么直接走到 $(x',y')$。

有一个细节问题在于如果最短路上的一个 $2$ 有一些儿子已经变成了 $0$，那么需要重新把这些 $0$ 指向这个 $2$ 才能继续进行下去。好在之前的所有讨论中都不会出现 Pulibot 站在一个 $0$ 上而 $4$ 个邻居中有 $2$ 的情况，所以直接让 Pulibot 走到这个 $0$ 并将这个 $0$ 指向那个 $2$ 即可。

代码实现：https://loj.ac/s/1880747。可以获得 $100$ 分。