每日一题

腐烂的苹果_牛客题霸_牛客网

思路分析:广度优先遍历，找到所有腐烂的苹果同时向四方扩散，就是第一轮把所有腐烂的苹果加入队列中，这就跟MQ的消息队列的原理差不多，第一次记录队列的长度，广度遍历一次，长度--并且四周为1的苹果变为腐烂状态(不是变成2 而是将状态数组变成true)，直到所有腐烂的苹果全部扩散完毕， 如果还有苹果的状态为1 return - 1

package study2.day5;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

//dfs 求 腐烂的苹果
public class Test5 {
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();
        boolean[][] vis = new boolean[m][n];//记录当前位置是否正在使用
        int[] dx = {0, 0, 1, -1};
        int ret = 0;
        int[] dy = {1, -1, 0, 0};//dx 和 dy 拼接成上下左右的坐标
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid.get(i).size(); j++) {
                if (grid.get(i).get(j) == 2){
                    queue.offer(new int[]{i, j});
                }
            }
        }
        while(!queue.isEmpty()){
            //队列不为空，就一次扩散，一次扩展全部腐烂的苹果
            int size = queue.size();
            while(size-- != 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 && y >= 0 && x < m && y < n && !vis[x][y] && grid.get(x).get(y) == 1){
                        vis[x][y] = true;//腐蚀掉
                        queue.offer(new int[]{x,y});//把被腐蚀掉的让他下一层再次扩展
                    }
                }
            }
            ret++;
        }
        //判断还有不能被腐蚀的苹果
        for (int i = 0; i < grid.size(); i++) {
            vis[i] = new boolean[grid.get(i).size()];
            for (int j = 0; j < grid.get(i).size(); j++) {
                if (grid.get(i).get(j) == 1 && !vis[i][j]){
                    return -1;
                }
            }
        }
        return ret - 1;
    }
}