778. Swim in Rising Water

这道题的前提是不能有相同海拔且海拔高度必须从0到n²-1
类dijkstra O(n²logn) time O(n²) space
这道题的难点是能看出来这其实是一个求最大边费用最小的最短路径（dijkstra）的题（和传统的求最小费用和的最短路径不一样），从一个点到邻居点的费用就是邻居点的海拔高度，这道题需要用dijkstra找到一条路径，使得路径上所有点的最高海拔高度尽可能小（这样就能用最少的时间从起点到终点），因为要维护尽可能小的海拔高度，所以要用堆，每次用堆顶的点的海拔高度来更新全局海拔高度，并将该点的邻接点入堆，至于选择四个方向的哪个邻居，完全基于贪心（dijkstra的本质），反正四个方向的邻居我们都会缓存起来，这样每次更新后实际上都会得到一个更大范围的包含最短路径的区域，在这道题里，这个区域的大小等于这个区域的海拔落差（最高海拔），并且该最短路径一定要经过这个最高海拔的点，因为（反证法）如果能找到另一条路径且最高海拔的点j比结果的最高海拔i要低，那么点j一定在点i之前入堆，且点i不可能入堆
跟1102. Path With Maximum Minimum Value 思路完全一样

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        auto cmp = [&](const pair<int, int> &lhs, const pair<int, int> &rhs) {return grid[lhs.first][lhs.second] > grid[rhs.first][rhs.second];};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        q.emplace(0, 0);
        vector<vector<bool>> visited(n, vector<bool>(n));
        visited[0][0] = true;
        int res = 0;
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!q.empty()) {
            auto p = q.top(); q.pop();
            res = max(res, grid[p.first][p.second]);
            if (p.first == n - 1 && p.second == n - 1) return res;
            for (int i = 0; i < 4; ++i) {
                int r = p.first + dr[i], c = p.second + dc[i];
                if (0 <= r && r < n && 0 <= c && c < n && !visited[r][c]) {
                    q.emplace(r, c);
                    visited[r][c] = true;
                }
            }
        }
        return -1;
    }
};

采用队列进行局部优化后

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        auto cmp = [&](const pair<int, int> &lhs, const pair<int, int> &rhs) {return grid[lhs.first][lhs.second] > grid[rhs.first][rhs.second];};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.emplace(0, 0);
        vector<vector<bool>> visited(n, vector<bool>(n));
        visited[0][0] = true;
        int res = 0;
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        while (!pq.empty()) {
            auto p = pq.top(); pq.pop();
            res = max(res, grid[p.first][p.second]);
            queue<pair<int, int>> q;
            q.push(p);
            while (!q.empty()) {
                auto p = q.front(); q.pop();
                if (p.first == n - 1 && p.second == n - 1) return res;
                for (int i = 0; i < 4; ++i) {
                    int r = p.first + dr[i], c = p.second + dc[i];
                    if (0 <= r && r < n && 0 <= c && c < n && !visited[r][c]) {
                        if (grid[r][c] <= res) {
                            q.emplace(r, c);
                        } else {
                            pq.emplace(r, c);
                        }
                        visited[r][c] = true;
                    }
                }
            }
        }
        return -1;
    }
};

二分+dfs O(n²logn) time
因为所有的海拔高度是从0到n²-1分布且最后答案一定在grid里面，所以适用二分查找，对于每一个candidate值，dfs遍历整个grid看是否能在candidate值以内（不超过）找到一条从grid[0][0]到grid[n - 1][n - 1]的路径

class Solution {
public:
    int swimInWater(vector<vector<int>>& grid) {
        n = grid.size();
        int lo = 0, hi = n * n - 1;
        while (lo < hi) {
            int m = lo + (hi - lo) / 2;
            if (isValid(grid, m)) {
                hi = m;
            } else {
                lo = m + 1;
            }
        }
        return lo;
    }

    bool isValid(const vector<vector<int>> &grid, int mx) {
        vector<vector<bool>> visited(n, vector<bool>(n));
        int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        return dfs(grid, visited, 0, 0, mx, dr, dc);
    }

    bool dfs(const vector<vector<int>> &grid, vector<vector<bool>> &visited, int r, int c, int mx, int dr[], int dc[]) {
        if (r < 0 || r >= n || c < 0 || c >= n || visited[r][c] || grid[r][c] > mx) return false;
        if (r == n - 1 && c == n - 1) return true;
        visited[r][c] = true;
        for (int i = 0; i < 4; ++i) {
            if (dfs(grid, visited, r + dr[i], c + dc[i], mx, dr, dc)) return true;
        }
        return false;
    }

    int n = 0;
};