Leetcode題解 Python & C#：五月挑戰DAY11 Flood Fill

給一個二維陣列，要把[sr][sc]位置上的顏色(值)換成 newColor，像是油漆桶工具，回傳取代過後的二維陣列。

這題是「遞迴函數」的基本題。

遇到在這種二維陣列的題型，選一個點上下左右找，為了避免同一位置重複找，用hash類紀錄找過的位置作檢查。

如果用 for迴圈 要思考整體是由左上至右下找，會不會因此有漏網之魚，如果有，還是得回歸 遞迴函數。

Python

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        rows, cols = len(image), len(image[0])
        oldColor = image[sr][sc]       
        
        @lru_cache(None)
        def search(y, x):
            if y < 0 or x < 0 or y == rows or x == cols:
                return 
            if image[y][x] == oldColor:
                image[y][x] = newColor
                search(y-1, x)
                search(y+1, x)
                search(y, x-1)
                search(y, x+1)            
                
        if oldColor != newColor: search(sr, sc)            
        return image

C#

public class Solution {
    int rows;
    int cols;
    public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
        var oldColor = image[sr][sc];
        rows = image.Length;
        cols = image[0].Length;
        if(oldColor != newColor)
        {
            Fill(image, sr, sc, newColor, oldColor);
        }
        return image;
    }
    
    public void Fill(int[][] image, int y, int x, int newColor, int oldColor)
    {
        if(y >= 0 && y < rows && x >= 0 && x < cols && image[y][x] == oldColor)
        {
            image[y][x] = newColor;
            Fill(image, y-1, x, newColor, oldColor);
            Fill(image, y+1, x, newColor, oldColor);
            Fill(image, y, x-1, newColor, oldColor);
            Fill(image, y, x+1, newColor, oldColor);
        }
    }    
}