778.水位上升的泳池中游泳

778.水位上升的泳池中游泳

题目

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

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

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

示例 1:

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

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

示例2:

输入: [[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

最终的路线用加粗进行了标记。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

提示:

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

思路

本体的思想和1631.最小体力消耗路径如出一辙。

首先我想到的是深度优先搜索/广度优先搜索找到水位高度最矮的路径。

但是，使用深度/广度优先搜索只能找到符合某个特定条件的路径，没有办法在搜索完毕后同时找到水位高度最矮的路径。

因此可以考虑将复杂问题转化为简单问题，即将原问题转化为两个相对简单的问题：

是否存在一条从左上角到右下角的路径，其经过的所有点的高度的最大值不超过 x？
这个x最小是几？

显然对问题1只需要对节点图进行一次深度/广度优先搜索即可解答，复杂度为O(n*n)。

然后对问题2，我们可以在x的所有候选集的范围中去进行二分搜索，找到这个最小的x，复杂度为O(logn*n)。

总的复杂度是O(n^2logn)。

本题的核心思想是，将一个复杂问题转化为两个相对简单问题的集合。通过分别解决这两个相对简单的问题，最终解决困难问题。

代码

下面代码可以对二分查找和广度优先搜索的写法进行一个很好的复习。

class Solution {
    private int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0,-1}}; // 方向盘
    public int swimInWater(int[][] grid) {
        int width = grid.length;
        int left = 0;
        int right = width * width - 1;
        int result = 0;
        while (left <= right) { // 二分搜索
            int mid = (left + right)/2;
            if (mid < grid[0][0]) { // 至少水位要高于起点高度，不然寸步难行
                left = mid + 1;
                continue;
            }
            Queue<int[]> queue = new LinkedList<int[]>();
            queue.offer(new int[]{0,0});
            int[][] seen = new int[width][width];
            int exist = 0;
            while (!queue.isEmpty()) { // 广度优先搜索
                int[] point = queue.poll();
                int x = point[0];
                int y = point[1];

                for (int[] direction : directions) {
                    int xnext = x + direction[0];
                    int ynext = y + direction[1];
                    if (xnext >= 0 && xnext < width
                    && ynext >= 0 && ynext < width
                    && grid[xnext][ynext] <= mid
                    && seen[xnext][ynext] == 0) {
                        if (xnext == (width - 1) && ynext == (width - 1)) {
                            exist = 1;
                            break;
                        } else {
                            queue.offer(new int[]{xnext, ynext});
                            seen[xnext][ynext] = 1;
                        }
                    }
                }
            }
            if (exist == 1) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}