This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is LeetCode 778. Swimming in a pool with rising water level, difficulty as difficult.

Tag: “minimum spanning tree”, “parallel search set”, “Kruskal”, “binary”, “BFS”

In an N x N grid grid, the value grid[I][j] of each grid represents the height of the platform at position (I,j).

It’s starting to rain now. When the time is t, the water level at any position in the pool caused by rainwater is T.

You can swim from one platform to any nearby platform, but only if the water level covers both platforms at the same time.

Assuming you can teleport an infinite distance, by default, it takes no time to swim around the grid.

Of course, you have to stay in the grid when you swim.

You start from the upper left platform of the grid (0,0). What is the minimum time it takes you to reach the lower right platform of the grid (n-1, n-1)?

 

Example 1:

Input: [[0,2],[1,3]] output: 3 explanation: when time is 0, you are in position (0, 0) on the grid. You can't swim in any direction because the four adjacent platforms are all higher than the water level when the current time is 0. Wait until the time is 3 before you can swim to the platform (1, 1). Since the water level is 3, no platform in the grid is higher than level 3, so you can swim to any position in the gridCopy the code

Example 2:

,1,2,3,4 input: [[0], [24,23,22,21,5], [12,13,14,15,16],,17,18,19,20 [11], [10,9,8,7,6]] output: 16: 0 12 3 4 12 13 14 15 16 11 10 9 8 7 6Copy the code

Tip:

  • 2 <= N <= 50.
  • The grid [I] is [j][0, ..., N*N - 1]The arrangement of.

Kruskal

Since you can move in any direction at any point, there is an undirected edge between adjacent points (four directions).

The weight of the edge WWW refers to the maximum height in a two-point node.

According to the meaning of the question, we need to find the optimal path from the upper left point to the lower right point, where the optimal path refers to the minimum maximum weight value of the path’s edge, and then input the maximum weight value in the optimal path.

We can first traverse all the points and add all edges to the set. The format of the storage is array [a, B, W][A,b,w][A,b,w], representing the weight between the point numbered AAA and the point numbered BBB is WWW (according to the meaning of the question, WWW is the maximum height of both).

Sort the collection, by WWW from arrive sort.

Once we have all of the sorted set of candidate edges, we can process edges from front to back, using and looking up the set to see if the point in the upper left corner is connected to the point in the lower right corner after each edge is added.

When we merge a certain edge, determine the connection between the upper left corner and the lower right corner of the point, then the weight of the edge is the answer.

This problem is almost exactly the same as 1631 the day before yesterday.

You could even copy the code from that problem and change the definition of WWW.

Code:

class Solution {
    int n;
    int[] p;
    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;
        
        // Initialize and look up the set
        p = new int[n * n];
        for (int i = 0; i < n * n; i++) p[i] = i;

        // Preprocess all edges
        // edge stores [a, b, w] : represents the time required to get from a to B
        // Although we can move in four directions, if we add "right" and "down" edges to each point, we have covered all edges
        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) {
                    int a = idx, b = getIndex(i + 1, j);
                    int w = Math.max(grid[i][j], grid[i + 1][j]);
                    edges.add(new int[]{a, b, w});
                }
                if (j + 1 < n) {
                    int a = idx, b = getIndex(i, j + 1);
                    int w = Math.max(grid[i][j], grid[i][j + 1]);
                    edges.add(new int[]{a, b, w}); }}}// In ascending order according to weight w
        Collections.sort(edges, (a,b)->a[2]-b[2]);

        // Add from the "small edge", when an edge is applied, the "starting point" and "node" are connected
        // Find the most weighted edge of the shortest path
        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)) {
                returnw; }}return -1;
    }
    int getIndex(int i, int j) {
        returni * n + j; }}Copy the code

The number of nodes is N ∗nn * nn∗n, and the number of undirected edges is strictly 2∗n∗(n−1)2 * N * (n-1)2∗n∗(n−1), an order of magnitude of n2n^2n2.

  • Time complexity: the complexity of obtaining all edges is O(n2)O(n^2)O(n2), the complexity of sorting is O(n2log⁡n)O(n^2\log{n})O(n2logn), and the complexity of traversing is O(n2)O(n^2)O(n2). The overall complexity is O(n2log⁡n)O(n^2\log{n})O(n2logn).
  • Space complexity: use and look up sets. The complexity is O(n2)O(n^2)O(n2).

Note: Assume that collections.sort () uses the dual-axis quicksort implementation in arrays.sort ().

The binary + BFS/DFS

In 1631. The path of minimum physical exertion, some students ask whether “two” can be used.

The answer is yes.

Topic given grid [I] [j] grid [I] [j] grid [I] [j] is the range of [0, n2-1] [n ^ 2-0, 1] is [0, n2-1], so the answer must be in this range.

Assume that the optimal solution is minminmin (exactly the time to reach the bottom right corner). Then the time less than minminmin cannot reach the lower right corner, while the time greater than minminmin can reach the lower right corner.

So in terms of the optimal solution
m i n min There are two segments on the number line of the split point, and the split point can be found by “dichotomy”
m i n min .

Note: the essence of dichotomy is dichotomy, not monotony. Dichotomy is used whenever one paragraph satisfies one property and the other does not. 33. Searching a rotated sort array is a good example.

Then, assuming that the optimal solution is minminmin, we perform dichotomy in the range of [L,r][L,r][L, R], when the current dichotomy time is midMIDmid:

  1. Min ⩽midmin \leqslant midmin⩽mid, r= MIDr =midr =mid

  2. Min >midmin >mid =mid+1l =mid+1l =mid+1

So once we’ve determined the dichotomy logic, we need to think about what do we write
c h e c k check Function.

Checkcheckcheck is a function that determines whether a given time/number of steps is from “start” to “finish”.

All we have to do is follow the rules and take a certain number of steps, checking to see if we’re at the end.

Checkcheckcheck can use both DFS and BFS. The idea is similar, so I’ll just take BFS as an example.

Code:

class Solution {
    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;
    }
    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;
    }
    boolean inArea(int n, int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n;
    }
    boolean canMove(int[][] grid, int[] from, int[] to, int time) {
        return time >= Math.max(grid[from[0]][from[1]], grid[to[0]][to[1]]); }}Copy the code
  • Time complexity: binary in the range of [0,n2][0, n^2][0,n2], complexity is O(log⁡n)O(\log{n})O(logn); A maximum of N2N ^ 2N2 nodes can join the BFS at a time, and the complexity is O(n2)O(n^2)O(n2). The overall complexity is O(n2log⁡n)O({n^2}\log{n})O(n2logn)
  • Spatial complexity: Use the Visited array. O(n2)O(n^2)O(n2)

The last

This is the No.788 article in our “Brush through LeetCode” series. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.