Rotting Oranges

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.

 

Example 1:

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

思路：跟Zombie in Matrix 一模一样：别忘记最后收集完下一层step++，下一层如果是空层，step空+1，后面要-1；

class Solution {
    private class Node {
        public int x;
        public int y;
        public int value;
        public Node(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value; // 0, 1, 2
        }
    }
    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<Node>();
        int n = grid.length;
        int m = grid[0].length;
        
        boolean[][] visited = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 2) {
                    queue.offer(new Node(i, j, 2));
                    visited[i][j] = true;
                }
            }
        }
        
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        
        int step = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                Node node = queue.poll();
                for(int k = 0; k < 4; k++) {
                    int nx = node.x + dx[k];
                    int ny = node.y + dy[k];
                    if(0 <= nx && nx < n && 0 <= ny && ny < m 
                       && !visited[nx][ny] && grid[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        queue.offer(new Node(nx, ny, 2));
                    }
                }
            }
            step++;
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == 1 && !visited[i][j]) {
                    return -1;
                }
            }
        }
        // 搜集完下一层，step++，但是最后一个空层，step空+1，所以要-1；
        return step == 0 ? 0 : step-1;
    }
}