图论-腐烂的橘子

994.腐烂的橘子

 
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
 
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
 
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。```
 
**输入**：二维数组
**输出**：最短时间
**思路**：看过题解本题使用BFS，广度优先算法，首先遍历数组，找到所有的“2”和“1”，然后统计，将“2”存在队列中，队列中的元素是数组，存的是“2”对应坐标，设置变量记录“1”的数，将所有的“2”存入队列中然后当做广度优先遍历的第0层，然后弹出，并将所能“污染”到的“1”进行“污染”，然后每一个“1”变为“2”，“1”的数量减一，最后判断是否大于0，大于0则返回最短时间，小于0则返回-1。
 
```java
class Solution {
    public int orangesRotting(int[][] grid) {
        //1的个数
        int num = 0;
        //2的坐标
        Queue<int[]> que = new LinkedList<>();
        //数组纬度
        int m = grid.length;
        int n = grid[0].length;
 
        //循环遍历数组
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 2){
                   que.add(new int[]{i , j});
                }else if(grid[i][j] == 1){
                    num++;
                }
            }
        }
        //时间
        int time = 0;
        while(num > 0 && !que.isEmpty()){
            time++;
            //把2的坐标记录下来
            //遍历2
            for(int i = 0; i < que.size(); i++){
                int[] pos = que.poll();
            int x = pos[0];
            int y = pos[1];
            //判断边界和1
            if(x + 1 < m && grid[x + 1][y] == 1){
                que.add(new int[]{x + 1, y});
                grid[x + 1][y] = 2;
                num--;
            }
            if(y + 1 < n && grid[x][y + 1] == 1){
                que.add(new int[]{x, y + 1});
                grid[x][y + 1] = 2;
                num--;
            }
            if(x - 1 > 0 && grid[x - 1][y] == 1){
                que.add(new int[]{x - 1, y});
                grid[x - 1][y] = 2;
                num--;
            }
            if(y - 1 > 0 && grid[x][y - 1] == 1){
                que.add(new int[]{x, y - 1});
                grid[x][y - 1] = 2;
                num--;
            }
            }
            
        }
        //还有1，返回-1
        if(num > 0){
            return -1;
        }
        return time;
    }
}复制