1631. 最小体力消耗路径

题目

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

示例 1：

输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。

示例 2：

输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
输出：1
解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。

示例 3：

输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出：0
解释：上图所示路径不需要消耗任何体力。

提示：

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 10^6

解答

思路

将本题抽象为如下的一个图论模型：

• 将地图中每一个格子看作 图中的一个节点
• 将两个相邻的格子（上下、左右）对应的节点之间连一条无向边，边的权值为高度差的绝对值
• 我们需要找一条从左上角到右下角的最短路径，路径的长度定义为经过 所有边权的最大值

建图：

• 由于地图是二维的，因此需要给每个节点赋予一个唯一的节点编号
• 地图的行数为 $n$，列数为 $m$，那么位置 $(i,j)$ 的格子对应的编号为 $i\times n+j$
• 这样二维地图格子编号对应 $[0,mn)$ 范围内的所有整数

二分查找

我们可以将这个问题转化成一个「判定性」问题，即：

是否存在一条从左上角到右下角的路径，其经过的所有边权的最大值不超过 $x$？

由于格子的高度范围是 $[1,{10}^6]$，因此可以对 $[0,{10}^6-1]$ 范围内的整数做二分查找，在每一步的查找中，我们对于当前的 $x$ 可以使用 DFS 或者 BFS 判断是否可以从左上角到达右下角，并根据判定结果更新二分查找的左边界或右边界。

代码：BFS

while (l < r) {
    int mid = (l + r) / 2;

    queue<pair<int, int>> q;
    q.emplace(0, 0);

    vector<bool> st(n * m);
    st[0] = true;

    while (q.size() != 0) {
        auto [x, y] = q.front();
        q.pop();

        for (int i = 0; i < 4; i ++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < m && st[nx * m + ny] == false
                && abs(heights[x][y] - heights[nx][ny]) <= mid) {
                q.emplace(nx, ny);
                st[nx * m + ny] = true;
            }
        }
    }

    if (st[n * m - 1]) {
        r = mid;
    }
    else {
        l = mid + 1;
    }
}

• 时间复杂度：$O(mn\log C)\approx {10}^5$ 可以通过，其中 $C$ 为高度差最大值
• 空间复杂度：$O(mn)$

并查集

• 我们将这 $mn$ 个节点放入并查集中，实时维护它们的连通性。
• 由于我们需要找到从左上角到右下角的最短路径，因此我们可以将图中的所有边按照 权值从小到大 进行排序，并依次加入并查集中
• 当我们加入一条权值为 $x$ 的边之后，如果左上角和右下角从非连通状态变为连通状态，那么 $x$ 即为答案。

代码：

• 时间复杂度：$O(mn\log mn)$

启发式搜索

定义加法运算 $a\oplus b=max(a,b)$，显然该运算满足交换律和结合律。那么如果一条路径上的边权分别为 $e_0,e_1,\cdots ,e_k$，那么 $e_0\oplus e_1\oplus \cdots \oplus e_k$ 就是这条路径的长度。