每日一题：最小体力消耗路径

题意

给定一个 $nm$ 的权值矩阵，求从左上角走到右下角。$(n, m \in [1, 100], w \in [1, 1e6])$

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

Solution

1. 二分答案：由于答案具有单调性，所以可以二分答案，然后通过 $bfs$ 进行验证。
2. 并查集：类似于最小生成树，将所有的边都建出来，然后贪心的将当前权值最小的边加入集合，判断起点和终点是否联通即可。
3. 最短路：将所有的边建出来，做一次起点到终点的最短路径即可。

Code

// 仅给出第二种做法的代码
class Solution {
public:
    // 并查集模板
    class UnionFind {
    public:
        vector<int> parent;
        vector<int> size;
        int n;
        // 当前连通分量数目
        int setCount;
        
    public:
        UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
            iota(parent.begin(), parent.end(), 0);
        }
        
        int findset(int x) {
            return parent[x] == x ? x : parent[x] = findset(parent[x]);
        }
        
        bool unite(int x, int y) {
            x = findset(x);
            y = findset(y);
            if (x == y) {
                return false;
            }
            if (size[x] < size[y]) {
                swap(x, y);
            }
            parent[y] = x;
            size[x] += size[y];
            --setCount;
            return true;
        }
        
        bool connected(int x, int y) {
            x = findset(x);
            y = findset(y);
            return x == y;
        }
    };
    struct Node {
        int x, y, w;
    };
    int minimumEffortPath(vector<vector<int>>& h) {
        int n = h.size(), m = h[0].size();
        vector<Node> g;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i > 0) g.push_back(Node{i * m + j, i * m + j - m, abs(h[i][j] - h[i - 1][j])});
                if (j > 0) g.push_back(Node{i * m + j, i * m + j - 1, abs(h[i][j] - h[i][j - 1])});
            }
        }
        sort(g.begin(), g.end(), [](Node& a, Node& b) -> bool {
            return a.w < b.w;
        });
        UnionFind uf(n * m);
        for (auto& p : g) {
            uf.unite(p.x, p.y);
            if (uf.connected(0, n * m - 1)) return p.w;
        }
        return 0;
    }
};