In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

image

1.思路

图的广度优先遍历。但有一个需要注意的是，这里由于邻接节点受到影响时算作rotten一次（每遍历一层算一次），所以每次都要全部取出queue里的上一个节点的邻接结点。

注意：
dx和dy是算出上下左右邻接点的算子,需要一 一对应，比如(i，j)的：[ i-1，j ]、[i，j-1]、[i+1，j]、[i，j+1]。

queue.size()不要放在for循环算，否则会拿到后面加入的结点。

2.代码实现

class Solution {
    int minutes;
    int row;
    int col;
    int[] dx = {-1, 0, 0, 1};
    int[] dy = {0, -1, 1, 0};

   public int orangesRotting(int[][] grid) {
        if (grid == null) return -1;
        row = grid.length;
        col = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        
        bfs(grid, queue);
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return minutes;
    }


    private void bfs(int[][] grid, Queue<int[]> queue) {
        while (!queue.isEmpty()) {
            boolean rotten = false;
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                int[] w = queue.poll();
                int x = w[0];
                int y = w[1];
                for (int i = 0; i < 4; i++) {
                    int tx = x + dx[i];
                    int ty = y + dy[i];
                    if (tx < 0 || ty < 0 || tx >= row || ty >= col || grid[tx][ty] == 2 || grid[tx][ty] == 0) {
                        continue;
                    }
                    queue.add(new int[]{tx, ty});
                    grid[tx][ty] = 2;
                    rotten = true;
                }
            }
            if (rotten) {
                ++minutes;
            }
        }
    }
}