恥ずかしながらFlood Fillって言葉をさっき知ったのでメモ.
An image is represented by an
m x n
integer gridimage
whereimage[i][j]
represents the pixel value of the image. You are also given three integerssr
,sc
, andcolor
. You should perform a flood fill on the image starting from the pixelimage[sr][sc]
. To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels withcolor
. Return the modified image after performing the flood fill.
NOTE:
image[i][j]
はピクセル値と表すimage[sr][sc]
から始まるimageにFlood fillを行いたい.- flood fillを行うためには, 開始ピクセルと, 開始ピクセルに4-directionally connectedな同じ色のピクセルと, それらのピクセルに4-directionally connectedな同じ色のピクセルを考える.
- 全ての上記の条件を満たすピクセルを
color
で置き換える
考えたこと
- 4-directionally connectedの意味を理解していなかったため, しばらく頭を悩ませた. これは, ただ単に開始ピクセルの四辺に接しているピクセルのなかで, 開始ピクセルと同じ色のピクセルは塗りつぶされるという意味だったのだが, 問題に添付されていた画像がすごくわかりにくかった. ペイントツールでのバケツ塗りと同じアルゴリズムだと考えれば納得がいった.
- 普通にDFSとかBFSとか使えば実装できそう.
実装
class Solution: def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]: row, column = len(image), len(image[0]) sColr = image[sr][sc] if sColr == color: return image def dfs(r, c): # dfs recursion if r < 0 or r>=row or c < 0 or c >= column or image[r][c] == color or image[r][c] != sColr: #invalid cases, just return return image[r][c] = color dfs(r+1, c) dfs(r-1, c) dfs(r,c+1) dfs(r, c-1)
エレガントじゃないかもですが通りました. わーい. 問題の意味がわからなくて怯みましたがEasyに分類されるのも納得.