Graph theory brush questions

1. The range of motion of the robot
2. Path in matrix
3. Image rendering
4. Swimming in a rising pool

778. Swimming in a rising pool

Try to catch up with the original question Address

Difficulty and label

It's difficult

• Depth-first traversal
• Breadth first traversal
• And find

Title Description

In a n x n The integer matrix of grid in , The value of each square grid[i][j] Indicate location (i, j) The height of the platform .

When it began to rain , In time for t when , The water level in the pool is t . You can swim from one platform to any nearby platform , But the premise is that the water level must submerge both platforms at the same time . Suppose you can move an infinite distance in an instant , That is to say, it is not time-consuming to swim inside the grid by default . Of course , You have to stay in the grid when you swim .

You go from the top left platform of the grid (0,0) set out . return You reach the lower right platform of the coordinate grid (n-1, n-1) Minimum time required .

Example 1：

 Input : grid = [[0,2],[1,3]]
 Output : 3
 explain :
 Time is 0 when , Your position in the grid is  (0, 0).
 You can't swim in any direction at this time , Because the heights of platforms in four adjacent directions are greater than the current time of  0  The water level at the end of the day .
 Wait for the time to arrive  3  when , You can swim to the platform  (1, 1).  Because the water level is  3, The platform in the coordinate grid has no comparison with the water level  3  Higher , So you can swim anywhere in the grid 

Example 2：

 Input : grid = [[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]]
 Output : 16
 explain :  The final route is marked in bold .
 We have to wait for time for  16, Only at this time can the platform be guaranteed  (0, 0)  and  (4, 4)  It's connected 

Tips :

• n == grid.length
• n == grid[i].length
• 1 <= n <= 50
• 0 <= grid[i][j] < n^2
• grid[i][j] Each value in No duplication

Topic analysis

The topic is very interesting , But it's really hard . First of all, a simple understanding of the scene can assume that we are a duck , From you to [0, 0] Swim home [n-1, n-1]. Note that swim get home , Therefore, the water must exceed the high platform to show that this road is accessible , Otherwise, the water is lower than the platform and you can't swim there .

Now combine the diagram 1, Be sure to wait until the water level reaches 3 Before you can pass .

Then we give the important conclusion of our reading topic ：

1. hypothesis W = Max(grid) , namely W Is the largest number of two-dimensional arrays , When the water level reaches W There must be a way , The lovely duckling will be able to go home .
2. Our answer must be [0, W] Between .

So this topic turns to finding a threshold threshold $\in [0,W]$ , bring , When the water level reaches threshold when , You can get at least one from [0, 0] To [n-1, n-1] The way home .

We have a two-dimensional array ary, Size is n x n, All defaults to 0.

Steps are as follows ：

1. Suppose the threshold is Q, For a two-dimensional array ary The position where the assignment is performed , The specific rules are ：

     If  grid[i][j] <=  threshold  Q, be  ary[i][j] = 1, It means that this point can pass . 
   

2. Traverse ary, Find out if there is a path [0, 0] To [n-1, n-1].

Obviously , If Q The bigger it is , The more points you can pass .

Code implementation 1—— DFS + Binary query

1. initialization visited Array ,visited[i][j] by true Indicates that you have accessed or cannot access .
2. Write a DFS function , Traverse all paths . If you can reach your destination （ get home ） Just go back to true;
3. Binary search threshold , Initialize each time according to the threshold visited Array , And then call DFS Function to check whether you can access .

Important supplement ：grid[0][0] The location is not necessarily 0, So the output is target Must be greater than or equal to grid[0][0]
, Therefore, the starting point of binary search is grid[0][0], According to the subject conditions, the maximum value is also less than n*n, So the end point of binary search is n*n-1.

class Solution {
    
public:
    const int dx[4] = {
    0, 1, 0, -1};
    const int dy[4] = {
    1, 0, -1, 0};
    /** *  initialization  visited  Array , Place the unqualified points in  true */
    void initVisited(vector<vector<int>> grid,
                     vector<vector<bool>>& visited,
                     int threshold) {
    
        int n = grid.size();
        for (int i=0; i<n; i++) {
    
            for (int j=0; j<n; j++) {
    
                visited[i][j] = grid[i][j] > threshold;
            }
        }
    }
    /** * dfs  Traverse  */
    bool dfs(vector<vector<bool>>& visited,
             int x, int y) {
    
        int n = visited.size();
        // 1.  Judge whether the destination is reached 
        if (x == n-1 && y == n-1) {
    
            return true;
        }
        // 2.  Tag has been accessed 
        visited[x][y] = true;
        
        // 3.  Depth-first traversal 
        for (int i=0; i<4; i++) {
    
            int mx = x + dx[i];
            int my = y + dy[i];
            if (mx >= 0 && mx < n && my >= 0 && my < n && !visited[mx][my] ) {
    
                //  If you reach the end  return  otherwise  continue for loop 
                if (dfs(visited, mx, my)) {
    
                    return true;
                }
            }
        }
        return false;
    }

    int swimInWater(vector<vector<int>>& grid) {
    
        int n = grid.size();
        int left = grid[0][0];
        int right = n*n-1;
        vector<vector<bool>> visited(n, vector<bool>(n));

        while (left < right) {
    
            int mid = (left+right)/2;
            initVisited(grid, visited, mid);
            if (dfs(visited, 0, 0)) {
    
                right = mid;
            } else {
    
                left = mid+1;
            }
        }
        // left == right
        return left;
    }
};

• Time complexity ：$O(N^2\log N)$
• Spatial complexity ：$O(N^2)$

Additional explanation ： If the topic does not emphasize the value range of each point , Then you can first find the largest and smallest , Then make a binary query , Same effect , Does not affect the overall time .

in addition , This problem is not the shortest path problem , The concern is how much water the ducklings can pass through , therefore , Even if there may be many paths in the end , We just need to make sure we have one that we can go with .

summary

It is basically the same as the official explanation , But the algorithm 1 My idea is to attach additional conditions to visited Array , dfs Basically nothing has changed .

If you understand the meaning of this topic , The only error prone thing should be Dichotomy search threshold . In fact, I passed all the test cases first and prompted to timeout , After reading the official source code, I remembered to find it by dichotomy .

In a word, it is an interesting topic , Never be difficult Two words bluff .

Smileyan
2022.3.22 17:08