題目描述:給定一個二維網格,每個格子可能是 0(空)、1(新鮮橘子)或 2(腐爛橘子)。每分鐘,腐爛橘子的四方向相鄰新鮮橘子會變腐爛。回傳所有橘子腐爛所需的最少分鐘數,若不可能全部腐爛則回傳 -1。
解題思路:這是「多源 BFS」的經典應用。同時從所有初始腐爛的橘子出發,每輪 BFS 擴展代表一分鐘。具體步驟:先掃描網格,將所有初始腐爛的橘子加入佇列,同時計算新鮮橘子數量 fresh。BFS 每次取出當前層的所有節點,向四方向擴展,使相鄰新鮮橘子腐爛並加入下一層,fresh 減一。每完成一層就將時間加一。最後若 fresh == 0 則回傳總時間,否則回傳 -1。
時間複雜度:O(m × n) — 每個格子最多入隊一次,m 和 n 分別為網格的行數與列數。
空間複雜度:O(m × n) — 佇列最壞情況下儲存所有格子(如棋盤格交錯排列的腐爛橘子)。
1. Scan grid: push all rotten (2) cells into queue, count fresh (1) cells
2. Initialize minutes = 0
3. While queue not empty AND fresh > 0:
a. Process all cells currently in queue (one BFS layer = one minute)
b. For each cell, check 4 neighbors:
- If neighbor is fresh (1): set to 2, decrement fresh, enqueue
c. Increment minutes
4. If fresh == 0: return minutes
5. Else: return -1 (some oranges unreachable)DFS + 時間標記 O(m²×n²):對每個新鮮橘子,DFS 找出距離最近的腐爛橘子,取所有橘子中的最大距離。時間複雜度較差,不推薦。
動態規劃(兩次掃描)O(m×n):從左上到右下掃描,再從右下到左上掃描,逐步更新每個格子的最短腐爛時間。僅適用於四方向移動的情況,思路較不直觀。