題目

  • 題目連結
  • 目標函式 : floodFill(image, sr, sc, color)
    • Input : image: List[List[int]]、sr: int、sc: int、color: int
    • Output : List[List[int]]

解題概念

  • 題意 :
    • image 由 m x n 整數陣列表示，其中 image[i][j] 表示 image 的 pixel value
    • 須從 image[sr][sc] 開始對 image 進行 Flood Fill
    • Flood Fill 的作法 : 考慮起始點，加上與四個方向與該點顏色相同的的點，再加上與四個方向與那些點顏色相同的的點，依此類推
    • 結果 : 將上述所有像素的顏色替換為 color

我的寫法

  • 想法 : 採用遞迴的方式
    1. 新增一個 check 的 m x n 布林陣列 : 預設為 false，若遞迴可以搜尋過則設為 true
    2. 使用 find(i, j) 去遞迴找出該格是否要換顏色 :
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    def floodFill(self, image, sr, sc, color):
        
        x = len(image)
        y = len(image[0])
        target = image[sr][sc]
        check = [[False for _ in range(y)] for _ in range(x)]

        def find(i, j):
            # 若 i 或 j 超出陣列範圍，則直接回傳 false
            if j < 0 or j >= y or i < 0 or i >= x:
                return False

            # 若該格尚未瀏覽過，且同時該格的值為 target，則回傳 true
            if not check[i][j] and image[i][j] == target :
                check[i][j] = True
            else:
                return False

            # 往左搜尋
            if find(i - 1, j) : 
                print("from ({},{}) tp ({},{})".format(i,j,i-1,j))
                image[i - 1][j] = color
            # 往右搜尋
            if find(i + 1, j) : 
                print("from ({},{}) tp ({},{})".format(i,j,i + 1, j))
                image[i + 1][j] = color
            # 往上搜尋
            if find(i, j - 1) : 
                print("from ({},{}) tp ({},{})".format(i,j,i, j - 1))
                image[i][j - 1] = color
            # 往下搜尋
            if find(i, j + 1) : 
                print("from ({},{}) tp ({},{})".format(i,j,i, j + 1))
                image[i][j + 1] = color
            return True

        find(sr, sc) # 從起始點開始
        image[sr][sc] = color
        return image
  • 成效 :
    • Runtime: 69 ms (faster than 7.46%)
    • Memory Usage: 13.7 MB (more than 15.50%)

解答 or 其他優秀寫法

  • 想法 : 與我的想法類似
    • 把我的寫法修得更加乾淨
    • 把 check 陣列移除
    • 在阻斷遞迴的地方新增 image[i][j] == color 與 image[i][j] != target 兩個條件
      • 後續就不須再去比較
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def floodFill(self, image, sr, sc, color):
        
        target = image[sr][sc]

        def find(i, j):
            if j < 0 or j >= len(image[0]) or i < 0 or i >= len(image) or image[i][j] == color or image[i][j] != target:
                return 

            image[i][j] = color
            find(i - 1, j)
            find(i + 1, j)
            find(i, j - 1)
            find(i, j + 1)

        find(sr, sc)
        return image
  • 成效 :
    • Runtime: 56 ms (faster than 75.81%)
    • Memory Usage: 13.5 MB (more than 56.70%)