class Solution {
public:
    bool isValid(int x,int y,int n,int m){
        return (x>=0 && x<n && y>=0 && y<m);
    }

    int minimumObstacles(vector<vector<int>>& grid) {
        queue<pair<int,int>>q;
        q.push({0,0});
        int n = grid.size();
        int m = grid[0].size();
        int dist[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dist[i][j] = INT_MAX/2;
            }
        }
        dist[0][0] = 0;
        while(q.size()){
            pair<int,int>p = q.front();
            q.pop();
            for(int i=-1;i<=1;i++){
                for(int j=-1;j<=1;j++){
                    if(abs(i)+abs(j)==1){
                        if(isValid(p.first+i,p.second+j,n,m)){
                            if(grid[p.first+i][p.second+j]==0){
                                if(dist[p.first][p.second]<dist[p.first+i][p.second+j]){
                                    q.push({p.first+i,p.second+j});
                                    dist[p.first+i][p.second+j] = dist[p.first][p.second];
                                }
                            }else{
                                if(dist[p.first][p.second]+1<dist[p.first+i][p.second+j]){
                                    q.push({p.first+i,p.second+j});
                                    dist[p.first+i][p.second+j] = dist[p.first][p.second]+1;
                                }                                
                            }
                        }
                    }
                }
            }
            
        }
        return dist[n-1][m-1];
    }
};