1631. 最小体力消耗路径

---

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/path-with-minimum-effort/

题目

---

你准备参加一场远足活动。给你一个二维 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] <= 106

以上图源均来自力扣（LeetCode）

解题思路

---

思路：并查集

先审题，题目给定一个 r o w s × c o l u m n s rows \times columns rows×columns 的地图 h e i g h t s heights heights，其中 h e i g h t s [ r o w ] [ c o l ] heights[row][col] heights[row][col] 表示的是 ( r o w , c o l ) (row, col) (row,col) 这个格子的高度。

现在题的背景的进行远足，出发的地点在左上角 ( 0 , 0 ) (0, 0) (0,0) 处，目的地在图的右下角 ( r o w s − 1 , c o l u m n s − 1 ) (rows-1, columns-1) (rows−1,columns−1) 处。允许每次往 上，下，左，右 四个方向移动，要求找出耗费体力最小的路径。

其中题目定义的耗费体力值，由相邻格子之间 高度差绝对值 的 最大值 决定。

即是，我们要找出一条路径，而这条路径格子之间相邻的 高度差绝对值 要尽可能的小。

其实本题可看是一个图模型：

• 将地图的每个格子看成是图的每个顶点；
• 将相邻格子用边进行相连，而边的权值为相邻两个格子之间 高度差绝对值；
• 要求找出一条从左上角到右下角的最短路径，而路径的长度取决于所有边的权值的最大值。

这里我们用并查集来解决这个问题，具体思路如下：

• 实现并查集数据结构；

注意，由于给定的地图是二维形式的，这里将每个格子映射在一维表格中，对应唯一的编号。

例如将第 i i i 行，第 j j j 列的格子映射在一维表格中，那么对应的索引应该是 i × n + j i \times n + j i×n+j，其中 n n n 表示列的宽度。

• 遍历，从图的左上角开始出发，向右向下开始添加边，由变量 e d g e s edges edges 存储连接相邻格子的边。这里边包含的元素 ( a , b , w i ) (a, b, wi) (a,b,wi)，其中 a , b a, b a,b 表示边连接的两个顶点，而 w i wi wi 表示边的权值，也就是相邻格子的高度差绝对值；
• 将 e d g e s edges edges 按照 w i wi wi（边的权值）大小进行升序排序；
• 开始遍历 e d g e s edges edges 中所有边，对两个顶点进行合并，遍历的同时判断左上角与右下角是否连通：
  • 若连通，那么此时 w i wi wi（边的权值）即是要求的答案（步骤 3 已经将边进行升序排序）
  • 否则，继续遍历合并边的顶点。

具体代码实现如下。

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
    
    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.parent[x_root] = y_root
    
    def connected(self, x, y):
        return self.find(x) == self.find(y)
        

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows = len(heights)
        cols = len(heights[0])

        edges = []

        for i in range(rows):
            for j in range(cols):
                # 格子映射在一维表格中
                idx = i * cols + j
                # 向右向下添加边
                # 边的元素 (a, b, wi)，a、b 表示边连接的顶点，wi 表示边的权值（相邻格子的高度差绝对值）
                if i < rows - 1:
                    edges.append((idx, idx + cols, abs(heights[i+1][j] - heights[i][j])))
                if j < cols - 1:
                    edges.append((idx + 1, idx, abs(heights[i][j+1] - heights[i][j])))
        # 按照边的权值升序排序
        edges.sort(key=lambda x:x[2])

        uf = UnionFind(rows * cols)
        # 遍历，合并顶点
        for x, y, wi in edges:
            uf.union(x, y)
            # 判断左下角与右下角是否连通
            # 连通，返回当前的边的权值
            if uf.connected(0, rows * cols - 1):
                return wi

        return 0                

欢迎关注

---

公众号 【书所集录】

---

如有错误，烦请指出，欢迎指点交流。若觉得写得还不错，麻烦点个赞