题解 | 腐烂的苹果

import java.util.*;

//多源bfs
public class Solution {
  //用于访问四周节点
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        Queue<int []> queue = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid.get(i).get(j)==2){//把烂苹果入队列
                    queue.add(new int[]{i,j});

                }
            }
            
        }
        int ret = 0;
        while(!queue.isEmpty()){//有烂苹果，开始腐烂
            int sz = queue.size();
            while(sz--!=0){//让所有烂苹果开始传染
                int[] t = queue.poll();
                int a = t[0],b=t[1];
                for(int i = 0; i < 4; i++){
                    int x = a+dx[i],y = b+dy[i];
                    if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y]&&grid.get(x).get(y)==1){//周围有苹果
                        vis[x][y] = true;//访问过了
                        queue.add(new int[]{x,y});//也变成了烂苹果，入队列，扩展下一层
                    }
                }
            
            }
            ret++;
        }//当队列为空，说明传染结束了
	  //此时如果还有1说明有苹果没有被污染
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid.get(i).get(j)==1&&!vis[i][j]){
                    return -1;//返回-1

                }
            }
            
        }
        
        
        return ret-1;
    }
}