腐烂的橘子 . 力扣994

￡神魔★判官ぃ 2023-10-01 21:34 19阅读 0赞

## 一、题目描述 ##

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16][]

## 二、思路 ##

本题与力扣 542 题 01 矩阵类似，都是使用层序遍历BFS

1.一开始，找出所有腐烂的橘子，将它们放入队列，作为遍历的第0层节点

2.然后进行BFS遍历，判断每个节点的上、下、左、右四个方向，注意判断到节点位于边界的情况

3.由于可能存在无法被污染的橘子，所以需要记录新鲜橘子的数量，在BFS遍历中，没污染一个橘子，就将新鲜橘子的数量减一。如果BFS遍历之后新鲜橘子的数量不为0，就说明存在无法被污染的橘子

## 三、代码实现 ##

class Solution {
        public int orangesRotting(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            Queue<int[]> queue = new LinkedList<>();
            //记录新鲜橘子的数量
            int count = 0;
            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){
                        queue.add(new int[]{i,j});
                    }
                }
            }
            //分钟数
            int round = 0;
            while(!queue.isEmpty() && count > 0){
                round++;
                int size = queue.size();
                for(int i = 0;i < size;i++){
                    int[] point = queue.poll();
                    int r = point[0];
                    int c = point[1];
                    //上、下、左、右遍历
                    if(r-1 >= 0 && grid[r-1][c] == 1){
                        grid[r-1][c] = 2;
                        count--;
                        queue.add(new int[]{r-1,c});
                    }
                    if(r+1 < m && grid[r+1][c] == 1){
                        grid[r+1][c] = 2;
                        count--;
                        queue.add(new int[]{r+1,c});
                    }
                    if(c-1 >= 0 && grid[r][c-1] == 1){
                        grid[r][c-1] = 2;
                        count--;
                        queue.add(new int[]{r,c-1});
                    }
                    if(c+1 < n && grid[r][c+1] == 1){
                        grid[r][c+1] = 2;
                        count--;
                        queue.add(new int[]{r,c+1});
                    }
                }
            }
            return count > 0 ? -1 : round;
        }
    }

##  ##

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3JhenlLLg_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/dad12e6723f545e1b487ac5289b9f39a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3JhenlLLg==,size_20,color_FFFFFF,t_70,g_se,x_16