2290. Minimum Obstacle Removal to Reach Corner

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).

• plain dfs solution with less memory useage then heap solution
• Time : O(nm)
• Space : O(nm)

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
        vector<vector<long long>> res(n, vector<long long>(m, INT_MAX));
        vector<vector<bool>> inc(n, vector<bool>(m, 0));
        queue<pair<int, int>> q;
        q.push({0,0});
        inc[0][0] = true;
        res[0][0] = 0;
        while(!q.empty()) {
            auto [y, x] = q.front(); q.pop();
            inc[y][x] = false;
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= ny and ny < n and 0 <= nx and nx < m) {
                    if(grid[ny][nx] == 0 and res[ny][nx] > res[y][x]) {
                        res[ny][nx] = res[y][x];
                        if(!inc[ny][nx]) {
                            q.push({ny, nx});
                            inc[ny][nx] = true;
                        }
                    } else if(grid[ny][nx] == 1 and res[ny][nx] > res[y][x] + 1) {
                        res[ny][nx] = res[y][x] + 1;
                        if(!inc[ny][nx]) {
                            q.push({ny, nx});
                            inc[ny][nx] = true;
                        }
                    }
                }
            }
        }
        
        return res[n-1][m-1];
    }
};

• heap soultion might be faster then bfs solution, but it uses more memory
• Time : O(nmlogk)
• Space : O(nm)

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
        vector<vector<int>> counter(n, vector<int>(m, INT_MAX));
        priority_queue<array<int,3>, vector<array<int,3>>, greater<array<int,3>>> q;
        q.push({0, 0,0});
        counter[0][0] = 0;
        while(!q.empty()) {
            auto [c, y, x] = q.top(); q.pop();
            if(counter[y][x] != c) continue;
            if(y == n - 1 and x == m - 1) return c;
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= ny and ny < n and 0 <= nx and nx < m) {
                    if(grid[ny][nx] == 0 and counter[ny][nx] > c) {
                        q.push({c, ny, nx});
                        counter[ny][nx] = c;
                    } else if(grid[ny][nx] == 1 and counter[ny][nx] > c + 1) {
                        q.push({c + 1, ny, nx});
                        counter[ny][nx] = c + 1;
                    }
                }
            }
        }

        return -1;
    }
};