994. Rotting Oranges - Medium

前往題目

之前的文章

想法

• BFS

思路

實作的時候條件判斷卡住，一段時間沒寫生疏了

1. 取得有幾個新鮮橘子(這樣才能知道要感染幾個)，以及初始的爛橘子在哪
2. BFS只關心腐爛橘子，感染其上下左右的橘子，直到感染所有橘子，或是觸碰不到剩餘的橘子
3. 如果還有剩餘新鮮橘子就回傳-1，反之回傳過了幾分鐘

Code

class Solution {
    public int orangesRotting(int[][] grid) {
        final int M = grid.length;
        final int N = grid[0].length;

        Queue<int[]> q = new LinkedList<>();

        List<int[]> directions = Arrays.asList(
            new int[]{1, 0},
            new int[]{-1, 0},
            new int[]{0, 1},
            new int[]{0, -1}
        );

        int fresh = 0;

        // Find the rotten orange
        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});
                } else if (grid[i][j] == 1) { // 紀錄新鮮橘子
                    ++fresh;
                }
            }
        }  

        int count = 0;

        // 直到沒有爛橘子或是新鮮橘子被感染完
        while (!q.isEmpty() && fresh != 0) {
            ++count;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                // 取出爛橘子的位置
                int[] rottenCell = q.poll();
                int r = rottenCell[0], c = rottenCell[1];
                
                // 感染其上下左右的橘子
                for (int[] direction : directions) {
                    int row = r + direction[0];
                    int col = c + direction[1];
                    // 確保界內
                    if (row < 0 || row >= M || col < 0 || col >= N) {
                        continue;
                    }
                    // 感染新鮮橘子
                    if (grid[row][col] == 1) {
                        // 被感染
                        grid[row][col] = 2;
                        // 加入之後要檢查的隊列
                        q.offer(new int[]{row, col});
                        // 少一顆新鮮橘子
                        --fresh;
                    }
                }
            }
        }
        return fresh == 0 ? count : -1;
    }
}