你准备参加一场远足活动。给你一个二维 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.lengthcolumns == heights[i].length1 <= rows, columns <= 1001 <= heights[i][j] <= 106
并查集。
并查集模板：
模板 1——朴素并查集：
# 初始化，p存储每个点的父节点
p = list(range(n))
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)模板 2——维护 size 的并查集：
# 初始化，p存储每个点的父节点，size只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
p = list(range(n))
size = [1] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
if find(a) != find(b):
size[find(b)] += size[find(a)]
p[find(a)] = find(b)模板 3——维护到祖宗节点距离的并查集：
# 初始化，p存储每个点的父节点，d[x]存储x到p[x]的距离
p = list(range(n))
d = [0] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
d[find(a)] = distance对于本题，每个格子当做图的一个节点，把相邻两个格子的高度差绝对值当做边的权重，因此本题是求解从最左上角的节点到最右下角的节点的连通性问题。
先把图中所有边去掉，然后按照边的权重从小到大，逐个把边添加上。如果在某一次添加一条边时，最左上角和最右下角的节点连通了，那么该边的权重就是题目的最小体力消耗值。
class Solution:
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
p = list(range(m * n))
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
e = []
for i in range(m):
for j in range(n):
if i < m - 1:
e.append([abs(heights[i][j] - heights[i + 1][j]), i * n + j, (i + 1) * n + j])
if j < n - 1:
e.append([abs(heights[i][j] - heights[i][j + 1]), i * n + j, i * n + j + 1])
e.sort()
for h, i, j in e:
p[find(i)] = find(j)
if find(0) == find(m * n - 1):
return h
return 0class Solution {
private int[] p;
public int minimumEffortPath(int[][] heights) {
int m = heights.length, n = heights[0].length;
p = new int[m * n];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i < m - 1) {
edges.add(new int[]{Math.abs(heights[i][j] - heights[i + 1][j]), i * n + j, (i + 1) * n + j});
}
if (j < n - 1) {
edges.add(new int[]{Math.abs(heights[i][j] - heights[i][j + 1]), i * n + j, i * n + j + 1});
}
}
}
Collections.sort(edges, Comparator.comparingInt(a -> a[0]));
for (int[] e : edges) {
int i = e[1], j = e[2];
p[find(i)] = find(j);
if (find(0) == find(m * n - 1)) {
return e[0];
}
}
return 0;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}class Solution {
public:
vector<int> p;
int minimumEffortPath(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
p.resize(m * n);
for (int i = 0; i < p.size(); ++i) p[i] = i;
vector<vector<int>> edges;
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i < m - 1) edges.push_back({abs(heights[i][j] - heights[i + 1][j]), i * n + j, (i + 1) * n + j});
if (j < n - 1) edges.push_back({abs(heights[i][j] - heights[i][j + 1]), i * n + j, i * n + j + 1});
}
}
sort(edges.begin(), edges.end());
for (auto e : edges)
{
int i = e[1], j = e[2];
p[find(i)] = find(j);
if (find(0) == find(m * n - 1)) return e[0];
}
return 0;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};var p []int
func minimumEffortPath(heights [][]int) int {
m, n := len(heights), len(heights[0])
p = make([]int, m*n)
for i := 0; i < len(p); i++ {
p[i] = i
}
var edges [][]int
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i < m-1 {
s := []int{abs(heights[i][j] - heights[i+1][j]), i*n + j, (i+1)*n + j}
edges = append(edges, s)
}
if j < n-1 {
s := []int{abs(heights[i][j] - heights[i][j+1]), i*n + j, i*n + j + 1}
edges = append(edges, s)
}
}
}
sort.Slice(edges, func(i, j int) bool {
return edges[i][0] < edges[j][0]
})
for _, e := range edges {
i, j := e[1], e[2]
p[find(i)] = find(j)
if find(0) == find(m*n-1) {
return e[0]
}
}
return 0
}
func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}