題目描述:給定一個二維整數矩陣 image,代表像素顏色,以及一個起始像素位置 (sr, sc) 和新顏色 color。請從起始像素出發,將所有與起始像素顏色相同且相連(上下左右四個方向)的像素改為新顏色,並回傳修改後的矩陣。
解題思路:這是一道經典的圖形遍歷問題,可以用 DFS(深度優先搜尋)或 BFS(廣度優先搜尋)解決。以 DFS 為例:
originalColor = image[sr][sc]。originalColor == color,無需任何操作,直接回傳(避免無限遞迴)。originalColor,則遞迴處理。需要特別注意的是「原始顏色與新顏色相同」的邊界情況——若不提前判斷,DFS 會因為像素已被改為新顏色(等於原色)而陷入無限遞迴。
時間複雜度:O(m × n) — 最壞情況下,整個矩陣的所有像素都與起始像素同色,DFS 需要訪問每一個像素恰好一次,其中 m 為列數、n 為行數。
空間複雜度:O(m × n) — 最壞情況下,遞迴呼叫堆疊的深度等於矩陣中的像素總數(例如蛇形排列時),因此需要 O(m × n) 的堆疊空間。
1. Record originalColor = image[sr][sc] 2. If originalColor == color, return image unchanged 3. Define DFS(r, c): a. If (r, c) is out of bounds, return b. If image[r][c] != originalColor, return c. Set image[r][c] = color d. Recursively call DFS on all 4 neighbors (up, down, left, right) 4. Call DFS(sr, sc) 5. Return the modified image
BFS 廣度優先搜尋 O(m × n):使用佇列(queue)代替遞迴,將起始像素加入佇列,逐層展開並染色所有同色相連像素。與 DFS 的時間複雜度相同,但避免了遞迴過深導致的堆疊溢位問題,在實際工程中更為穩健。
迭代 DFS(使用顯式堆疊)O(m × n):用顯式 stack 取代系統遞迴堆疊,模擬 DFS 的行為。同樣可以避免遞迴深度過深的問題,且記憶體使用可預測,適合對堆疊深度有限制的環境。