# 2290. Minimum Obstacle Removal to Reach Corner
###### tags: `Leetcode` `Hard` `BFS`
Link: https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner/
## 思路
层序遍历的变式

本题的本质就是从起点到终点，采用层级BFS，最少需要穿越几个回合的障碍。而障碍与障碍之间的空气，可以忽略不计。也就是说，某个障碍与空气相邻的话，下一个回合可以通过空气到达其他的障碍。

在实现过程中，除了常规的层级BFS之外，我们还需要有一个getNext的函数。我们还需要有一个getNext的函数，遍历所有能“隔空”访问的障碍物。这些障碍物需要加入下一回合BFS的队列中去。
## Code

class Solution {
    int ans = 0;
    int[][] dirs = new int[][]{{-1,0},{1,0},{0,1},{0,-1}};
    public int minimumObstacles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0,0});
        int step = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int[] curr = q.poll();
                if(curr[0]==m-1 && curr[1]==n-1) return step-1;
                List<int[]> neighbors = getNext(curr, grid);
                for(int[] neigh:neighbors) q.add(neigh);
            }
            step++;
        }
        return -1;
    }
    private List<int[]> getNext(int[] curr, int[][] grid){
        List<int[]> result = new ArrayList<>();
        Queue<int[]> q = new LinkedList<>();
        q.add(curr);
        while(!q.isEmpty()){
            int[] pos = q.poll();
            for(int[] dir:dirs){
                int newx = pos[0]+dir[0];
                int newy = pos[1]+dir[1];
                if(newx<0 || newx>=grid.length || newy<0 || newy>=grid[0].length || grid[newx][newy]==-1) continue;
                if(grid[newx][newy]==1){
                    result.add(new int[]{newx, newy});
                }
                if(newx==grid.length-1 && newy==grid[0].length-1){
                    result.add(new int[]{newx, newy});
                    return result;
                }
                else if(grid[newx][newy]==0){
                    q.add(new int[]{newx, newy});
                }
                grid[newx][newy]=-1;
            }
        }
        return result;
    }
}