BFS搜索

回溯做了一星期，都是用dfs，今天刚好每日一题是bfs

994. 腐烂的橘子 - 力扣（LeetCode）

m x n 网格 grid 中：

值 0 代表空单元格；

值 1 代表新鲜橘子；

值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]

输出：4

bfs其实就是层序遍历 ，用队列+迭代那一套来做这一题，思路如下：

遍历一遍，找：
- 腐烂的橘子，加进初始队列
- 新鲜的橘子数，记作count
bfs：
- 对腐烂的橘子，四周如果有橘子
  - 设为腐烂，并加进下一层队列
  - count–
如果count不为0，说明有橘子未被处理

class Solution {
    public int orangesRotting(int[][] grid) {
        //创建链表，把污染节点放进去，并统计为1个数
        int count=0, ans=0, m=grid.length, n=grid[0].length;
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        Queue<int[]> que = new LinkedList<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j]==1) count++;
                else if(grid[i][j]==2) que.add(new int[]{i,j});
            }
        }
        //bfs，把污染节点
        while(count>0 && !que.isEmpty()){
            ans++;
            int k=que.size();
            while(k-->0){
                int[] badPoint = que.poll();
                for(int[] dir:dirs){
                    int curPointX = badPoint[0]+dir[0], curPointY = badPoint[1]+dir[1];
                    if(curPointX>=0 && curPointX<m && curPointY>=0 && curPointY<n && grid[curPointX][curPointY]==1){
                        count--;
                        que.add(new int[]{curPointX, curPointY});
                        grid[curPointX][curPointY] = 2;
                    }
                }
            }
        }
        return count>0?-1:ans;
    }
}