LeetCode 994. 腐烂的橘子

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

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

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

示例 1：

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

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

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

提示：

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

思路：为了省事，直接用|=4标记马上要腐烂的橘子.

class Solution {

    private static final int[] dx = new int[]{0,0,1,-1};
    private static final int[] dy = new int[]{1,-1,0,0};

    public int orangesRotting(int[][] grid) {
        int length1 = grid.length, length2 = grid[0].length;
        int minutes = 0 , rotting = 4;
        boolean change = true ,allRotting = true;

        while(change){
            change = false; // 初始化为false
            for(int i = 0;i < length1;i++){
                for(int j = 0 ;j < length2;j++){
                    if( grid[i][j] == 2 ){
                        for(int k = 0;k < 4;k++){
                            int x = i + dx[k];
                            int y = j + dy[k];
                            if(x >= 0 && x < length1 && y >= 0 && y < length2 && grid[x][y] == 1){
                                grid[x][y] |= rotting;
                            }
                        }
                    }
                }
            }

            for(int i = 0;i < length1; i++){
                for(int j = 0; j < length2; j++){
                    if( (grid[i][j] & rotting) != 0 ){
                        change = true;
                        grid[i][j] = 2;
                    }
                }
            }

            if(change) minutes++; //如果腐烂了，添加时间
        }


        for(int i = 0; i < length1; i++){
            for(int j = 0; j < length2; j++){
                if( grid[i][j] == 1)
                    allRotting = false;
            }
        }

        return allRotting == false ? -1 : minutes;
    }
}