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

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

思路：

这题用0-1BFS，显然有障碍的格子cost为1，无障碍的格子cost为0，比较明显的0-1了。建立dist表来记录从0点到{x, y}点的最短距离dist[x][y]，建立visited表来记录{x, y}点是否已经更新为最短距离了。之后就是deque双端队列进行BFS，对于4个方向中，cost为1的下一步，放入deque的后端，cost为0的下一步，放入deque的前端，这样就保证了我们从deque中拿出的永远都先是低消耗的点。最后只需要返回dist[m - 1][n - 1]即可。

代码：

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];
    }
};