洛谷 P9605 题解

璀璨星空1 · 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 分。