1102. Path With Maximum Minimum Value

最小边费用最大的最短路径O(RClogRC) time O(RC) space
跟778. Swim in Rising Water思路完全一样
类dijkstra
用最大堆 只找大数 然后沿着大数走 同时用大数来更新结果 直到达到目的地

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int R = A.size(), C = A[0].size();
        vector<vector<bool>> visited(R, vector<bool>(C));
        auto cmp = [&A](const auto &a, const auto &b) { return A[a.first][a.second] < A[b.first][b.second]; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.emplace(0, 0);
        visited[0][0] = true;
        int res = INT_MAX, dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!pq.empty()) {
            auto [r, c] = pq.top(); pq.pop();
            res = min(res, A[r][c]);

            if (r == R - 1 && c == C - 1) return res;
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i];
                if (0 <= rr && rr < R && 0 <= cc && cc < C && !visited[rr][cc]) {
                    pq.emplace(rr, cc);
                    visited[rr][cc] = true;
                }
            }

        }
        return res;
    }
};

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int R = A.size(), C = A[0].size();
        vector<vector<bool>> visited(R, vector<bool>(C));
        auto cmp = [&A](const auto &a, const auto &b) { return A[a.first][a.second] < A[b.first][b.second]; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.emplace(0, 0);
        visited[0][0] = true;
        int res = INT_MAX, dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!pq.empty()) {
            auto [r, c] = pq.top(); pq.pop();
            res = min(res, A[r][c]);

            // 优化：找出从(r, c)开始的一个范围，该范围内的所有点的费用都不超过A[r][c]
            // 因为用的是queue，不用入堆，局部上使用了复杂度更低的数据结构，但整体的检查规模并没有本质变化
            queue<pair<int, int>> q;
            q.emplace(r, c);
            while (!q.empty()) {
                auto [r, c] = q.front(); q.pop();
                if (r == R - 1 && c == C - 1) return res;
                for (int i = 0; i < 4; ++i) {
                    int rr = r + dr[i], cc = c + dc[i];
                    if (0 <= rr && rr < R && 0 <= cc && cc < C && !visited[rr][cc]) {
                        if (A[rr][cc] < res) {
                            pq.emplace(rr, cc);
                        } else { // 不小于结果的数不会对结果产生影响，继续扩大局部搜索区域
                            q.emplace(rr, cc);
                        }
                        visited[rr][cc] = true;
                    }
                }
            }

        }
        return res;
    }
};

union-find

class Solution {
public:
    int maximumMinimumPath(vector<vector<int>>& A) {
        int R = size(A), C = size(A[0]);
        parent.resize(R * C);
        iota(begin(parent), end(parent), 0);
        vector<pair<int, int>> v;
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                v.emplace_back(r, c);
            }
        }
        auto cmp = [&A](const auto &a, const auto &b) { return A[a.first][a.second] > A[b.first][b.second]; };
        sort(begin(v), end(v), cmp);
        vector<bool> visited(R * C);
        int dr[] = {0, 0, 1, -1}, dc[] = {1, -1, 0, 0};
        for (const auto &[r, c] : v) {
            int k = r * C + c;
            visited[k] = true;
            for (int i = 0; i < 4; ++i) {
                int rr = r + dr[i], cc = c + dc[i], kk = rr * C + cc;
                if (rr < 0 || rr >= R || cc < 0 || cc >= C || !visited[kk]) continue;
                merge(k, kk); // 只有visit过的才去union，否则代码不好写
            }
            if (find(0) == find(R * C - 1)) return A[r][c];
        }
        return -1;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x), py = find(y);
        parent[py] = px;
    }

    vector<int> parent;
};