01BFS.cpp

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> distance(n, vector<int>(m, INT_MAX));
        deque<pair<int, int>> lwh;
        distance[0][0] = grid[0][0];
        lwh.push_back({0, 0});
        vector<vector<int>> dir = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
        while (!lwh.empty()) {
            auto [l, r] = lwh.front();
            lwh.pop_front();
            if (l == n - 1 && r == m - 1)
                return distance[l][r];
            for (vector<int>& k : dir) {
                int ii = l + k[0], jj = r + k[1];
                if (ii >= 0 && ii < n && jj >= 0 && jj < m) {
                    int dis = distance[l][r] + grid[ii][jj];
                    if (dis < distance[ii][jj]) {
                        distance[ii][jj] = dis;
                        if (grid[ii][jj] == 0)
                            lwh.push_front({ii, jj});
                        else
                            lwh.push_back({ii, jj});
                    }
                }
            }
        }
            return distance[n - 1][m - 1];
        }
    };