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.思路

圖的廣度優(yōu)先遍歷失乾。但有一個(gè)需要注意的是沃缘，這里由于鄰接節(jié)點(diǎn)受到影響時(shí)算作rotten一次（每遍歷一層算一次）攀例，所以每次都要全部取出queue里的上一個(gè)節(jié)點(diǎn)的鄰接結(jié)點(diǎn)。

注意：
dx和dy是算出上下左右鄰接點(diǎn)的算子,需要一 一對(duì)應(yīng)，比如(i音比，j)的：[ i-1，j ]、[i苛萎，j-1]、[i+1，j]腌歉、[i蛙酪，j+1]。

queue.size()不要放在for循環(huán)算翘盖，否則會(huì)拿到后面加入的結(jié)點(diǎn)桂塞。

2.代碼實(shí)現(xiàn)

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;
            }
        }
    }
}