本文主要是介绍力扣--并查集1631.最小体力消耗路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这题将图论和并查集联系起来。把数组每个位置看成图中的一个节点。
这段代码的主要思路是：
- 遍历地图中的每个节点，将每个节点与其相邻的下方节点和右方节点之间的边加入到边集合中（因为从上到下和从下到上他们高度绝对值一样的，所以只要考虑下方和右方）。
- 对所有的边按照其权重（高度差绝对值）进行升序排序。
- 遍历排序后的边集合，依次将每条边所连接的节点合并到一个集合中，并检查左上角节点和右下角节点是否已经连通。
- 当左上角节点和右下角节点连通时，返回当前边的权重，即为最小体力消耗值。
class Solution {int all; // 所有节点的数量int n, m; // 地图的行数和列数int fa[100001]; // 并查集数组，用于记录每个节点的父节点// 并查集的查找操作，寻找根节点int find(int x) {if (fa[x] == x)return x;else return find(fa[x]);}// 并查集的合并操作，将两个节点所在的集合合并void togother(int x, int y) {fa[find(x)] = find(y);}// 边的结构体，用于表示两个节点之间的边以及边的权重typedef struct edge {int u; // 边的起始节点int v; // 边的结束节点int weight; // 边的权重（高度差绝对值）} edge;// 将二维坐标转换为一维索引int getIndex(int i, int j) {return i * m + j;}// 静态比较函数，用于排序边，按照权重升序排序static bool cmp(const edge &x1, const edge &x2) {return x1.weight < x2.weight;}public:int minimumEffortPath(std::vector<std::vector<int>>& heights) {n = heights.size(); // 获取地图的行数m = heights[0].size(); // 获取地图的列数all = n * m; // 计算地图中格子的总数// 初始化并查集，每个节点的父节点初始为自身for (int i = 0; i < all; i++)fa[i] = i;vector<edge> edges; // 存储所有可能的边// 遍历地图上的每个节点，构建边for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int idx1 = getIndex(i, j); // 当前节点的索引// 计算当前节点与下方节点的边if (i + 1 < n)edges.push_back({idx1, getIndex(i + 1, j), abs(heights[i][j] - heights[i + 1][j])});// 计算当前节点与右方节点的边if (j + 1 < m)edges.push_back({idx1, getIndex(i, j + 1), abs(heights[i][j] - heights[i][j + 1])});}}// 按照边的权重进行升序排序sort(edges.begin(), edges.end(), cmp);// 遍历所有的边for (int i = 0; i < edges.size(); i++) {// 将当前边所连接的两个节点合并到同一个集合中togother(edges[i].u, edges[i].v);// 如果起始节点和终止节点在同一个集合中，即左上角节点和右下角节点连通if (find(0) == find(getIndex(n - 1, m - 1)))return edges[i].weight; // 返回当前边的权重，即最小体力消耗值}return 0; // 默认情况下返回0，表示没有路径}
};这篇关于力扣--并查集1631.最小体力消耗路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
