994. Rotting Oranges

https://leetcode.com/problems/rotting-oranges/

思路跟 1162 差不多, 只是要注意一些條件

和 fresh 的橘子的個數會影響到結果,

還有要看清楚 題目的 “例子”

ex2這樣會是 -1, ex3 會是 0

O(nm), O(nm)

class Solution {
    int dirs[][] = {{0,1}, {0,-1}, {1,0}, {-1, 0}};
    public int orangesRotting(int[][] grid) {
        int m = grid.length; //height
        if (m == 0) {
            return -1;
        }
        int n = grid[0].length; //width
        
        int freshCount = 0;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.offer(new int[]{i, j}); //rotten (x,y) add to q first
                } else if (grid[i][j] == 1) { // count fresh
                    freshCount++;
                }
            }
        }
        if (freshCount == 0) { //ex3的情況
            return 0;
        }
        
        int count = -1;
        while (!q.isEmpty()) {
            count++;
            int levels = q.size();

            for (int i = 0; i < levels; i++) {
                int rotten[] = q.poll();
                int r = rotten[0];
                int c = rotten[1];
                
                for (int d[] : dirs) {
                    int r0 = r + d[0];
                    int c0 = c + d[1];
                    if (inArea(r0, c0, grid) && grid[r0][c0] == 1) {
                        grid[r0][c0] = 2;
                        q.offer(new int[]{r0, c0}); // 加入新的 rotten
                        freshCount--;
                    }
                }
            }
        }
        return freshCount == 0 ? count : -1; // -1: ex2的情況
    }
    
    private boolean inArea(int r, int c, int[][] grid) {
        return (r >= 0 && r < grid.length && c >=0 && c < grid[0].length);
    }
}

2021/9/04 version

/*
0 - no oranges
1 - fresh
2 - rotten

use BFS, 

add rotten to queue
count fresh one's count

if a cell has rotten, make it's neightbor cell (if it's fresh) become rotten (like spread disease), fresh--


*/
class Solution {
    private static final int DIRECTIONS[][] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        
        int freshCount = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new int[]{i,j});
                }
                if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        if (freshCount == 0) return 0;
        
        int result = -1; // why?
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cell[] = queue.poll();
                int x = cell[0];
                int y = cell[1];
                
                for (int[] direction : DIRECTIONS) {
                    int newX = x + direction[0];
                    int newY = y + direction[1];
                    if (inArea(grid, newX, newY) && grid[newX][newY] == 1) {
                        grid[newX][newY] = 2; // makes it rotten
                        queue.add(new int[]{newX, newY});
                        freshCount--;
                    }
                }
            }
            result++; 
        }
        
        return freshCount == 0 ? result : -1;
    }
    
    private boolean inArea(int grid[][], int x, int y) {
        return (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length);
    }
}