2290. Minimum Obstacle Removal to Reach Corner

subject ：

You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:

• 0 represents an empty cell,
• 1 represents an obstacle that may be removed.

You can move up, down, left, or right from and to an empty cell.

Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).

Example 1:

Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2).
It can be shown that we need to remove at least 2 obstacles, so we return 2.
Note that there may be other ways to remove 2 obstacles to create a path.

Example 2:

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 105
• 2 <= m * n <= 105
• grid[i][j] is either 0 or 1.
• grid[0][0] == grid[m - 1][n - 1] == 0

Ideas ：

This question uses 0-1BFS, A grid with obvious obstacles cost by 1, Barrier free grid cost by 0, Quite obvious 0-1 了 . establish dist Table to record from 0 Point to {x, y} The shortest distance of a point dist[x][y], establish visited Table to record {x, y} Whether the point has been updated to the shortest distance . After is deque Double ended queue BFS, about 4 In all directions ,cost by 1 Next step , Put in deque Backend ,cost by 0 Next step , Put in deque The front end of the , This ensures that we start from deque Always take out the low consumption points first . Finally, just go back dist[m - 1][n - 1] that will do .

Code ：

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        dist[0][0] = 0;
        deque<pair<int, int>> q;
        vector<pair<int, int>> dirt = { {1, 0}, {-1, 0}, {0 , 1}, {0, -1} };
        q.push_back({ 0, 0 });
        while (q.size()) {
            auto tmp = q.front();
            q.pop_front();
            int x = tmp.first, y = tmp.second;
            if (visited[x][y]) {
                continue;
            }
            visited[x][y] = true;
            for (int i = 0; i < dirt.size(); i++) {
                int nx = x + dirt[i].first;
                int ny = y + dirt[i].second;
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
                    continue;
                }
                dist[nx][ny] = min(dist[nx][ny], dist[x][y] + grid[nx][ny]);
                if (grid[nx][ny] == 1) {
                    q.push_back({ nx, ny });
                } else {
                    q.push_front({ nx, ny });
                }
            }
        }
        return dist[m - 1][n - 1];
    }
};