2258. Escape from the fire (attached: understanding of binary search)

Today’s article was written with my new keyboard. Hey, record it!

The following are notes based on the explanation of the Lingcha Mountain Aifu Up Master:

In the binary search code, pay attention to the opening and closing of the left and right intervals, which can be divided into closed intervals, left-closed right-open intervals, left-open and right-open intervals, which can solve three problems: > = > <= <, generally solves the first problem, the other three can be converted into the first expression, for example, >x is equivalent to >=(x + 1), <=x is equivalent to (>=x)-1, is equivalent to (>x)-1, and >x is equivalent to >=(x + 1), so we only need to learn how to solve the problem of >=x Just solve it.
Be sure to pay attention to the opening and closing of binary search intervals and the problems to be solved

def sort(nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1 # Closed interval [left, right]
while left <= right: # The range is not empty
# In C++ or Java programming language, pay attention to the overflow problem of left and right addition
# mid = (left + (right - left)) // 2
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # [mid + 1, right]
else:
right = mid - 1 # [left, mid-1]
return left

def sort(nums: List[int], target: int) -> int:
left = 0
right = len(nums) # Left closed and right open interval [left, right)
while left < right: # The range is not empty
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # [mid + 1, right）
else:
right = mid # [left, mid）
return left # right

def sort(nums: List[int], target: int) -> int:
left = -1
right = len(nums) #Open interval (left, right)
while left + 1 < right: # The range is not empty
mid = (left + right) // 2
if nums[mid] < target:
left = mid # (mid, right)
else:
right = mid # (left, mid)
return right

My initial solution to this problem was closer to the second method, which was to use breadth-first search to compare the difference between the fire path and the human path.
But I didn’t think comprehensively enough, so I came up with the following ideas based on the solution:
First, calculate the shortest time for people to arrive at each grid arriveTime and the time for fire to arrive at each grid fireTime, and conduct classification discussions

  1. If arriveTime is less than 0, the representative cannot reach the safe house and returns -1
  2. Otherwise (arriveTime is greater than 0), if fireTime is less than 0, it means that the fire cannot reach the safe house. People and fire are separated, so the waiting time of people can be infinite. Return 1e9
  3. Otherwise, arriveTime is greater than 0 and fireTime is greater than 0, that is, both humans and fire can reach the safe house, then: d=fireTime[m-1][n-1]-arriveTime[m- 1][n-1]
  4. If d is less than 0, it means that the time for fire to reach the safe house is less than the time for people to reach the safe house. If the fire reaches the safe house first, it cannot stay and returns -1
  5. Otherwise (d is greater than or equal to 0), it means that the time for the fire to arrive at the safe house is greater than or equal to the time for the person to arrive at the safe house, and the fire will arrive later or arrive at the safe house at the same time as the person.
  6. If d is greater than 0, then the fire reaches the safe house, then determine the time when the fire and the person arrive in the grid except the end point (that is, the grid to the left and above the end point). If the person arrives before the fire at this time, return d, otherwise d-1 is returned.

Code:

class Solution {<!-- -->
public:
    constexpr static int dirs[4][2] = {<!-- -->{<!-- -->-1, 0}, {<!-- -->1, 0}, {<!- - -->0, -1}, {<!-- -->0, 1}};
    constexpr static int INF = 1e9;
    int maximumMinutes(vector<vector<int>> & amp; grid) {<!-- -->
        int m = grid.size(), n = grid[0].size();
        //The time each grid is on fire
        vector<vector<int>> fireTime(m, vector<int>(n, INF));
        // bfs calculates the time for each grid to catch fire
        bfs(grid, fireTime);
        //The shortest time from starting point to end point
        int arriveTime = getArriveTime(grid, fireTime, 0);

        // Classification discussion
        // 1. The safe house is inaccessible
        if (arriveTime < 0) {<!-- -->
            return -1;
        }
        // 2. The safe house is accessible, but the fire is inaccessible.
        if (fireTime[m-1][n-1] == INF) {<!-- -->
            return INF;
        }
        // 3. Both humans and fire can be reached, but the time when fire arrives earlier than humans ans
        int ans = fireTime[m-1][n-1] - arriveTime;
        // 4. ans < 0, then the fire arrives before the person, return -1
        // 5. ans >= 0, then the fire arrives after the person, then determine whether the person arrives at the left and upper grid of the safe house before the fire after staying for ans minutes.
        // 6. If possible, return ans; otherwise, return ans-1
        return getArriveTime(grid, fireTime, ans) >= 0 ? ans : (ans - 1);
    }

    void bfs(vector<vector<int>> & amp;grid, vector<vector<int>> & amp;fireTime){<!-- -->
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        // init
        for (int i = 0; i < m; i + + ) {<!-- -->
            for (int j = 0; j < n; j + + ) {<!-- -->
                if (grid[i][j] == 1){<!-- -->
                    q.emplace(i, j);
                    fireTime[i][j] = 0;
                }
            }
        }

        int time = 1;
        while (!q.empty()) {<!-- -->
            int sz = q.size();
            for (int i = 0; i < sz; i + + ) {<!-- -->
                auto [cx, cy] = q.front();
                q.pop();
                for (int j = 0; j < 4; j + + ) {<!-- -->
                    int nx = cx + dirs[j][0];
                    int ny = cy + dirs[j][1];
                    if (nx >= 0 & amp; & amp; ny >= 0 & amp; & amp; nx < m & amp; & amp; ny < n) {<!-- -->
                        if (grid[nx][ny] == 2 || fireTime[nx][ny] != INF) {<!-- -->
                            continue;
                        }
                        q.emplace(nx, ny);
                        fireTime[nx][ny] = time;
                    }
                }
            }
            time + + ;
        }
    }

    int getArriveTime(vector<vector<int>> & amp;grid, vector<vector<int>> & amp;fireTime, int stayTime){<!-- -->
        int m = grid.size(), n = grid[0].size();
        queue<tuple<int, int, int>> q;
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        q.emplace(0, 0, stayTime);
        visit[0][0] = true;
        while (!q.empty()) {<!-- -->
            auto [cx, cy, time] = q.front(); // Note that the time here is the time that the current grid needs to stay
            q.pop();
            for (int j = 0; j < 4; j + + ) {<!-- -->
                int nx = cx + dirs[j][0];
                int ny = cy + dirs[j][1]; //nx and ny represent the marked grid, which has not yet arrived. If it arrives, time needs + 1
                if (nx >= 0 & amp; & amp; ny >= 0 & amp; & amp; nx < m & amp; & amp; ny < n) {<!-- -->
                    if (grid[nx][ny] == 2 || visit[nx][ny]) {<!-- -->
                        continue;
                    }
                    if (nx == m - 1 & amp; & amp; ny == n - 1) {<!-- --> // So it takes time + 1 to reach the end here
                        return time + 1;
                    }
                    if (fireTime[nx][ny] > time + 1) {<!-- --> // The time it takes for the fire to reach the target node and the time it takes for people to reach it
                        visit[nx][ny] = true;
                        q.emplace(nx, ny, time + 1);
                    }
                }
            }
        }
        return -1;
    }
};

In addition, compared to q.push, the queue enqueue operation q.emplace essentially passes the parameters of the constructor and constructs the object directly in the memory, eliminating the need for movement. process.

syntaxbug.com © 2021 All Rights Reserved.