LeetCode LCP 31 - 变换的迷宫
题目链接:LeetCode LCP 31 - 变换的迷宫(LCCUP 21 春季赛第 4 题)
思路
题目表示我们可以使用两个权利各一次:
- 永久性改变
- 暂时性改变
也就是说在第 \(i\) 个时刻,如果小力位于 \((x, y)\),此时有四种情况:
- 未使用「永久性改变」,未使用「暂时性改变」
- 未使用「永久性改变」,已使用「暂时性改变」
- 已使用「永久性改变」,未使用「暂时性改变」
- 已使用「永久性改变」,已使用「暂时性改变」
我们可以用这几个常量来表示这四种情况(与上面一一对应):
1 | const int |
我们可以根据当前时刻 \(i\)、当前坐标 \((x, y)\),以及当前的权利使用情况(即上面四种,记这个量为 \(\rm s\),\(s \in \{ 0, 1, 2, 3 \}\)),这几个量作为状态,来递推结果,方法有点类似「分层图最短路」的思想。
设 \(f(i, x, y, s)\) 表示从 \(0\) 时刻、\((0, 0)\) 点、未使用任何权利,到当前时刻为 \(i\),在坐标 \((x, y)\),权利使用情况为 \(s\) 的最小时间。
类似于单源最短路径算法,我们把 \(f(0, 0, 0, {\rm NONE\_USED})\) 初始化为 \(0\),剩下的所有状态对应的 \(f\) 设置为 \(+\infty\),然后把二元组 \(((i, x, y, s), f(i, x, y, s))\) 扔进队列,开始做 BFS。在拓展新的状态时:
- 新状态的 \(i\) 用旧状态的 \(i\) 加 \(1\) 得到,表示从 \(i\) 时刻转移到 \(i + 1\) 时刻
- 新状态的 \((x', y')\) 用旧状态的 \((x, y)\) 分别叠加这五个增量:
- \((0, 0)\)
- \((0, 1)\)
- \((0, -1)\)
- \((1, 0)\)
- \((-1, 0)\)
下面我们来对新状态的 \(s\) 进行讨论。
- 当地图上 \({\rm mazes}(i, x, y)\) 是
.
,即可行时,对 \((i, x, y, s)\) 和 \((i + 1, x', y', s)\) 做一次松弛,即如果 \(f(i, x, y, s) + 1 < f(i + 1, x', y', s)\),就令 \(f(i + 1, x', y', s) = f(i, x, y, s) + 1\),然后把二元组 \(((i + 1, x', y', s), f(i + 1, x', y', s))\) 加入队列。 - 当地图上 \({\rm mazes}(i, x, y)\) 是
#
,即不可行时,要对 \(s\) 进行分类:- 如果 \(s = {\rm ONLY\_TEMP}\),即未使用「永久性改变」,已使用「暂时性改变」,我们需要使用一次「永久性改变」来「打通」这个位置,那么 \(s\) 将由 \({\rm ONLY\_TEMP}\) 变成 \({\rm TEMP\_PERM}\),即我们要在 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm TEMP\_PERM})\) 之间做一次松弛
- 如果 \(s = {\rm ONLY\_PERM}\),这个时候要判断是对哪个点使用了「永久性改变」
- 如果正好是当前 \((x', y')\),那么我们可以直接松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', s)\)
- 如果并不是当前 \((x', y')\),我们需要使用一次「临时性改变」,即需要松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm TEMP\_PERM})\)
- 此时我们发现,我们需要一个重要的新信息,即如果小力已经使用了「永久性改变」,我们需要知道他使用在哪个位置,这个信息在前文的讨论中是没有记录下来的。把它记录下来的办法有很多种,在这里我们可以把 \(f(i, x, y, s)\) 从一个数扩展成一个结构体,这个结构体里记录三个量 \((d, x_p, y_p)\),其中整数 \(d\) 就是我们之前定义的 \(f\) 的值,\((x_p, y_p)\) 表示小力在 \((x_p, y_p)\) 处使用了「永久性改变」。这个「扩展」也许不是一开始就想到的,是我们在慢慢形成思路的过程中想到的。如果我们决定使用「永久性改变」,这里的 \((x_p, y_p)\) 也要随之更新。
- 如果 \(s = {\rm NONE\_USED }\),我们既可以选择使用一次「临时性改变」,也可以选择使用一次「永久性改变」
- 如果选择「临时性改变」,则松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm ONLY\_TEMP})\)
- 如果选择「永久性改变」,则松弛 \((i, x, y, s)\) 和 \((i + 1, x', y', {\rm ONLY\_PERM})\)
- 如果 \(s = {\rm TEMP\_PERM }\),则两次权利都已经使用,没有办法走到这个点
最后,如果在任意一个时刻 \(i\),任意一种 \(s\) 的情况下,终点的 \(f\) 的值不是 \(+\infty\),说明终点是可达的。
代码
1 | using LL = long long; |
复杂度
- 时间复杂度:\(O(t \times n \times m \times 4) = O(t \times n \times m)\),其中 \(t\) 代表时刻总数。
- 空间复杂度:\(O(t \times n \times m)\)。