【刷穿 LeetCode】778. 水位上升的泳池中游泳（困难）

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

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

class Solution {
    int n;
    int[] p = new int[2509];
    void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    boolean query(int a, int b) {
        return find(a) == find(b);
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public int swimInWater(int[][] grid) {
        n = grid.length;
        List<int[]> edges =  new ArrayList<>();
        for (int i = 0; i < n ;i++) {
            for (int j = 0; j < n; j++) {
                int idx = getIndex(i, j);
                p[idx] = idx;
                if (i + 1 < n) edges.add(new int[]{idx, getIndex(i + 1, j), Math.max(grid[i][j], grid[i + 1][j])});
                if (j + 1 < n) edges.add(new int[]{idx, getIndex(i, j + 1), Math.max(grid[i][j], grid[i][j + 1])});
            }
        }
        Collections.sort(edges, (a,b)->a[2]-b[2]);
        int start = getIndex(0, 0), end = getIndex(n - 1, n - 1);
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1], w = edge[2];
            union(a, b);
            if (query(start, end)) return w;
        }   
        return -1;
    }
    int getIndex(int i, int j) {
        return i * n + j;
    }
}

class Solution {
    private final int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
    public int swimInWater(int[][] grid) {
        int n = grid.length;
        int l = 0, r = n * n;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(grid, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
    private boolean check(int[][] grid, int time) {
        int n = grid.length;
        boolean[][] visited = new boolean[n][n];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{0, 0});
        visited[0][0] = true;
        while (!queue.isEmpty()) {
            int[] pos = queue.pollFirst();
            int x = pos[0], y = pos[1];
            if (x == n - 1 && y == n - 1) return true;

            for (int[] dir : dirs) {
                int newX = x + dir[0], newY = y + dir[1];
                int[] to = new int[]{newX, newY};
                if (inArea(n, newX, newY) && !visited[newX][newY] && canMove(grid, pos, to, time)) {
                    visited[newX][newY] = true;
                    queue.addLast(to);
                }
            }
        }
        return false;
    }
    private boolean inArea(int n, int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
    private boolean canMove(int[][] grid, int[] from, int[] to, int time) {
        return time >= Math.max(grid[from[0]][from[1]], grid[to[0]][to[1]]);
    }
}

class Solution {
    int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
    int[][] grid;
    boolean[] st;
    int n;
    public int swimInWater(int[][] _grid) {
        grid = _grid;
        n = grid.length;
        int l = 0, r = n * n;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return r;
    }
    boolean check(int t) {
        // st 和 d 装的都是 (x,y) 转换出来的 idx
        // 由 (x,y) 得 idx: idx = x * n + y
        // 由 idx 得 (x,y): x = idx / n, y = idx % n;
        st = new boolean[n * n];
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0); // 等同 a.addLast(0 * n + 0); 
        st[0] = true; // 等同 st[0 * n + 0] = true; 
        int end = (n - 1) * n + (n - 1);
        while (!d.isEmpty()) {
            int idx = d.pollFirst();
            if (idx == end) return true;
            int x = idx / n, y = idx % n;
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                // 将一些赋值为 true 的表达式嵌在判断条件里的写法其实并不冷门，在 Java 不少数据结构实现中都有（ConcurrentHashMap...）
                // 我这里采用这种写法的目的是为了可以少写一对大括号，同时将下面的四行代码在一行内写完。这里为了大家看着方便，我分为了四行
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
                        !st[nx * n + ny] &&
                            t >= Math.max(grid[x][y], grid[nx][ny]) &&
                                (st[nx * n + ny] = true)) d.addLast(nx * n + ny);
            }
        }
        return false;
    }
}