P3799. 寻找最优的路测线路

解题思路

为什么不能使用动态规划

题目要求从左上角找到一条路线到右下角，该条路线中的最小值要尽可能地大。

本题很容易和路径类的 dp 问题混淆（例如 不同路径、不同路径 II、最小路径和 等等）。 但本题和该类路径 dp 问题有一个非常明显的不同：前者移动方向是上下左右，而后者的移动方向只有向下和向右。 本题如果使用 dp 的话，动态转移方程并不明确，因为转移的方向是未知的，不满足 dp 的无后效性。 因此本题不能用 dp 来解决。

启发式搜索

寻路类型的问题，除了 dp，很容易想到使用 DFS 或者 BFS 来解决。 但本题显然不应该使用 DFS，因为 DFS 在寻路问题中本质上就是回溯穷举，在 20 * 20 = 400 的数据规模下必然超时。 因此思考如何用 BFS 解决该问题。

传统的 BFS 过程，用队列维护，先入队的节点必然先出队被考虑。但这种传统做法并不能满足该题目的要求。

首先考虑人脑是如何思考这个问题的。以题目所给的示例为例：

从值为 5 的起点 (0, 0) 出发，有两个近邻点可以选择，分别是 (0, 1) 和 (1, 0)。 但我们会优先选择 (0, 1) 作为路线的下一个点，因为 (0, 1) 的值为 4 大于 (1, 0) 的值 1，能使得当前路线中的最小值更大。

选择了 (0, 1) 之后，下一个可能的近邻点为三个，包括 (0, 2)、(1, 0) 和 (1, 1)，它们的值分别为 5、1、2。 类似地，我们会优先选择 (0, 2) 作为路线的下一个点，因为 (0, 2) 的值为 5，是这三个近邻点中值最大的。

依照上述规律，每次我们都会选择所有近邻点中值最大的那个作为下一个点，直到到达终点。 接下来我们会依次选择 (1, 2) 和 (2, 2)，到达右下角终点，完成 5 -> 4 -> 5 -> 6 -> 6 的路线。

所以，在搜索过程中，每次出队的节点不再是按照入队先后顺序弹出的，而是按照最大值作为优先级来弹出的。 显然以某种优先级作为出队依据，应该使用优先队列来代替队列。

这种包含了贪心思想的搜索方式并非传统的 BFS，称之为启发式搜索（Heuristic Search）。

> PS：不熟悉优先队列的话，排序后取出最大值也是可以的，在当前数据规模下是可以通过所有用例的。

复杂度分析

• 设栅格为 R 行 C 列，格子总数记为 R×C。
• 启发式搜索中，每个格子在入堆的同时就被 check_list 标记为已检查，因此每个格子至多入堆一次、出堆一次；堆的大小不超过 R×C，单次入堆或出堆的代价为 O(log(R×C))。
• 每次出堆后只考察上下左右四个近邻，属常数次判断，因此整个搜索的时间复杂度为 O(R×C × log(R×C))，瓶颈在优先队列的插入与弹出操作。
• 空间复杂度为 O(R×C)：grid 本身、check_list 检查数组与优先队列各占一份与格子总数同阶的空间。
• Python 版本用 heapq 存节点值的相反数模拟大根堆，C++ 版本直接用 priority_queue 大根堆，两者渐进复杂度一致。