994. Rotting Oranges

994. Rotting Oranges

題目的說明

題目有說明的有，腐爛的橘子會影響旁邊的好橘子，好橘子會爛掉，如果好橘子相連的好橘子有和爛橘子相連，過了一段時間後也會爛掉，如果有橘子沒有和任何的爛橘子相鄰就不會壞掉。

除了題目有說明的點以外，還有幾個條件要先確定好：

1. 如果所有橘子都是壞掉的，那要回傳的時間為零

2. 如果一個橘子都沒有，回傳的時間為零

3. 如果所有橘子都是好的，回傳的時間為 -1

這個題目的技巧在於，一開始要把所有的爛掉的橘子放在出發點，並且透過 BFS 同時出發，當全部的橘子都探索完了，就可以知道要花多少時間了，所需要花的時間就是 BFS 所走的層數。

這裡有另外一個點是，要如何知道有沒有橘子壞掉？第一個直覺的方法是全部感染完後，重新掃描看看還有沒有好的橘子就好了，其實這樣做不會造成太多的理論時間複雜度的差別，但是這樣會讓 code 變得很複雜。

第二個方法是我們一開始的時候就計算出有多少的新鮮的橘子，在 BFS 時，只要有一個橘子壞掉了，我們就減一，最後只要判斷，如果新鮮的橘子沒了，就是所有的橘子都感染完成了。

最後有一個地方要注意，那就是到了最後一步，我們會放進去的是壞掉的橘子，這樣會讓 BFS 多走一步，有兩個方法可以選擇

1. 在做 BFS 的同時，也要確保還有新鮮的橘子 while queue and fresh_oranges > 0 ，這樣也合理，如果已經沒有新鮮的橘子了，就不需要再探索了。

2. 不要加上上面的條件，直接在最後的 mins - 1 就好了，兩種條件都可以通過。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        queue = deque()
        fresh_oranges = 0

        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh_oranges += 1

        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        mins = 0
        
        if not queue and fresh_oranges > 0:
            return -1
        
        if fresh_oranges == 0:
            return mins
        
        # BFS 
        while queue and fresh_oranges > 0:            
            mins += 1
            for _ in range(len(queue)):
                row, col = queue.popleft()
                for dr, dc in directions:
                    next_row = row + dr
                    next_col = col + dc
                    if 0 <= next_row < rows and 0 <= next_col < cols: 
                        if grid[next_row][next_col] == 1:
                            queue.append((next_row, next_col))
                            grid[next_row][next_col] = 2
                            fresh_oranges -= 1
        
        return mins if fresh_oranges == 0 else -1