力扣 leetcode 1631. 最小体力消耗路径 （python）_力扣 163确实的区间

Topic

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

Example_1

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

Example_2

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

Example_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
解释：上图所示路径不需要消耗任何体力。

Tips

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106

Solution

由于这是一道典型的求最小路径连通问题
我们可以利用Kruskal算法的思想来解决
Kruskal算法详解（点击查看）
并查集字典模板
并查集列表连通模板

由于本题没有一个确切的节点可供遍历和添加到并查集中
所以本题中解法用列表的索引值不同来区分不同的节点
之后的方法都是利用

首先我们可以将其全部转换为[权重，边的开始，边的结束]的形式

第一步 计算权重

在这道题中
权重指的就是两个节点间（这条边）的节点值之差
不断遍历heights中的节点
计算差值的绝对值，同时将两个节点加入到列表total中

第二步 根据权重对边排序

就是按照total的第一位进行排序

第三步 判断并查集是否连通

首先初始化一个并查集uf
在这里可以令并查集节点数n为heights中边的个数
但我们也可以设置一个较大的值例如10000来替代节点数

之后遍历排序后的边：
按照权重从小到大连接边
若连通则直接返回当前边的权重total[0]

在这里可以无需用判断是否只有一个连通分量的方式判断是否连通
可以通过判断首节点和尾节点是否连通
若联通则路径有效

Code

class UnionFind:
    def __init__(self, n):
        self.father = list(range(n))
        self.size = [1] * n
        self.n = n
        # 当前连通分量数目
        self.setCount = n
    
    def find(self, x):
        if self.father[x] == x:
            return x
        self.father[x] = self.find(self.father[x])
        return self.father[x]
    
    def merge(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.father[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True
    
    def is_connected(self, x, y):
        return self.find(x) == self.find(y)

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        uf = UnionFind(10000)
        total = []
        m = len(heights)
        n = len(heights[0])

        for i in range(m):
            for j in range(n):
                pos = i * n + j
                if i < m - 1:
                    total.append([abs(heights[i + 1][j] - heights[i][j]), pos, pos + n])
                if j < n - 1:
                    total.append([abs(heights[i][j + 1] - heights[i][j]), pos, pos + 1])
        total.sort()     

        for sizes in total:
            uf.merge(sizes[1], sizes[2])
            if uf.is_connected(0, m * n - 1):
                return sizes[0]
        return 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

Result