题目描述

在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。

现在开始下雨了。当时间为 t 时，此时雨水导致水池中任意位置的水位为 t。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台 (N-1, N-1)？

样例

输入：[[0,2],[1,3]]
输出：3
解释：
时间为 0 时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。

等时间到达 3 时，你才可以游向平台 (1, 1)。
因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置。

输入：
[[0,1,2,3,4],
 [24,23,22,21,5],
 [12,13,14,15,16],
 [11,17,18,19,20],
 [10,9,8,7,6]
]
输入：16
解释：
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

最终的路线为 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 16 -> 
15 -> 14 -> 13 -> 12 -> 11 -> 10 -> 9 -> 8 -> 7 -> 6。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的。

提示

• 2 <= N <= 50
• grid[i][j] 是 [0, ..., N * N - 1] 的一个排列。

算法

(二分答案 + 连通性判断) $O(n^2 \log n)$

1. 显然最终的答案有单调性的，我们二分一个天数作为答案。
2. 根据这个天数，用宽度优先遍历或者深度优先遍历或者并查集算法判断起点和终点是否连通。
3. 注意，如果天数小于 grid[0][0] 的情况。

时间复杂度

• 二分答案需要 $O(\log n)$ 次，每次需要 $O(n^2)$ 的时间判定答案，故总时间复杂度为 $O(n^2 \log n)$。

空间复杂度

• 需要额外 $O(n^2)$ 的空间判定连通性。

C++ 代码

class Solution {
public:
    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};

    bool check(vector<vector<int>> &grid, int limit) {
        int n = grid.size();
        queue<pair<int, int>> q;
        vector<vector<int>> vis(n, vector<int>(n, false));

        if (grid[0][0] > limit)
            return false;

        vis[0][0] = true;
        q.push(make_pair(0, 0));

        while (!q.empty()) {
            auto u = q.front();
            q.pop();

            for (int i = 0; i < 4; i++) {
                int tx = u.first + dx[i], ty = u.second + dy[i];
                if (tx < 0 || tx >= n || ty < 0 || ty >= n ||
                    vis[tx][ty] || grid[tx][ty] > limit)
                    continue;

                vis[tx][ty] = true;
                q.push(make_pair(tx, ty));
            }
        }

        return vis[n - 1][n - 1];
    }

    int swimInWater(vector<vector<int>>& grid) {
        int n = grid.size();
        int l = 0, r = n * n - 1;

        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(grid, mid))
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }
};