LeetCode 994. Rotting Oranges

原题链接在这里：https://leetcode.com/problems/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.

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

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

题解：

Iterate grid, for rotten orange, add it to the queue, for fresh orange, count++.

Perform BFS, when neibor is fresh, mark it as rotton and add to que, count--.

If eventually count == 0, then all rotton. return level.

Time Complexity: O(m * n). m = grid.length. n = grid[0].length.

Space: O(m * n).

AC Java:

class Solution {
    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0){
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        LinkedList<int []> que = new LinkedList<>();
        int cnt = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 2){
                    que.add(new int[]{i, j});
                }else if(grid[i][j] == 1){
                    cnt++;
                }
            }
        }
        
        if(cnt == 0){
            return 0;
        }
        
        int [][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int level = -1;
        while(!que.isEmpty()){
            level++;
            int size = que.size();
            while(size-- > 0){
                int [] cur = que.poll();
                grid[cur[0]][cur[1]] = 2;
                
                for(int [] dir : dirs){
                    int x = cur[0] + dir[0];
                    int y = cur[1] + dir[1];
                    if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 1){
                        continue;
                    }
                    
                    grid[x][y] = 2;
                    cnt--;
                    que.add(new int[]{x, y});
                }
            }
        }
        
        return cnt == 0 ? level : -1;
    }
}

类似Walls and Gates, Shortest Distance from All Buildings.