994：腐烂的橘子

问题描述

在给定的网格中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

示例

输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示

• 1 <= grid.length <= 10
• 1 <= grid[0].length <= 10
• grid[i][j] 仅为 0、1 或 2

思路

这题可以先把为2的橘子搞到一个队列中，然后从队头搞出来元素判定能不能感染四周的橘子。如果感染了四周的橘子，那么count++, 还要进行下一轮感染。如果没有能感染，那么得遍历一下grid看看有没有落单的橘子，如果有，返回-1。如果没有，则返回count。(方法一)
这种情况下，如果grid中没有橘子，则根本不会进到queue中，所以是正确的。

这种递归的方式实现bfs(其实是伪bfs，因为我图省空间把已经遍历过的坏橘子也加入queue了，应该是只加入新的被感染的橘子)，效率应该不如迭代，所以改成迭代的。（方法二）

方法一

Java版

class Solution {
    private Queue<Element> queue = new LinkedList<>();
    private int count = 0;
    public int orangesRotting(int[][] grid) {
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 2){
                    Element element = new Element(i,j);
                    queue.add(element);
                }
            }
        }
        boolean flag = false;
        while(!queue.isEmpty()){
            Element cur = queue.poll();
            if(0<cur.i && grid[cur.i-1][cur.j] == 1){
                grid[cur.i-1][cur.j] = 2;
                flag = true;
            }
            if(cur.i<grid.length-1&&grid[cur.i+1][cur.j] == 1){
                grid[cur.i+1][cur.j] = 2;
                flag = true;
            }
            if(0<cur.j && grid[cur.i][cur.j-1] == 1){
                grid[cur.i][cur.j-1] = 2;
                flag = true;
            }
            if(cur.j<grid[0].length-1&&grid[cur.i][cur.j+1] == 1){
                grid[cur.i][cur.j+1] = 2;
                flag = true;
            }
        }
        if(!flag){
            for(int[] row:grid){
                for(int elem: row){
                    if(elem == 1){
                        return -1;
                    }
                }
            }
            return count;
        }
        count++;
        return orangesRotting(grid);
    }
}
class Element{
    int i;
    int j;
    Element(int i,int j){
        this.i = i;
        this.j = j;
    }
}

方法二

Java版

class Solution {
    private Queue<Element> queue = new LinkedList<>();
    private int count = 0;
    public int orangesRotting(int[][] grid) {
        int count1 = 0,count2 = 0;
        for(int[] row:grid){
            for(int elem:row){
                if(elem == 1){
                    count1++;
                }else if(elem == 2){
                    count2++;
                }
            }
        }
        if(count2 == 0){
            if(count1 > 0){
                return -1;
            }
            return 0;
        }
        init(queue,grid);
        Queue<Element> tmp = new LinkedList<>();
        while(queue.size()>0){
            while(queue.size() > 0){
                Element e = queue.poll();
                if(0<e.i && grid[e.i-1][e.j] == 1){
                    grid[e.i-1][e.j] = 2;
                    tmp.add(new Element(e.i-1,e.j));
                }
                if(e.i<grid.length-1 && grid[e.i+1][e.j] == 1){
                    grid[e.i+1][e.j] = 2;
                    tmp.add(new Element(e.i+1,e.j));
                }
                if(0<e.j && grid[e.i][e.j-1] == 1){
                    grid[e.i][e.j-1] = 2;
                    tmp.add(new Element(e.i,e.j-1));
                }
                if(e.j<grid[0].length-1 && grid[e.i][e.j+1] == 1){
                    grid[e.i][e.j+1] = 2;
                    tmp.add(new Element(e.i,e.j+1));
                }
            }
            if(tmp.size() == 0){
                for(int[] row:grid){
                    for(int elem:row){
                        if(elem == 1){
                            return -1;
                        }
                    }
                }
            }else{
                count++;
                Queue<Element> t = queue;
                queue = tmp;
                tmp = t;
            }
        }
        return count;
    }
    private void init(Queue<Element> queue,int[][] grid){
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 2){
                    queue.add(new Element(i,j));
                }
            }
        }
    }
}
class Element{
    int i;
    int j;
    Element(int i,int j){
        this.i = i;
        this.j = j;
    }
}