【LeetCode】733. Flood Fill 解答・解説【Python】

学習メモ

自分の言葉で書くことで理解できていない部分をハッキリさせたい。

問題
1. 原文
2. 内容
解答
補足・参考・感想

問題

原文

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[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 with color.

Return the modified image after performing the flood fill.

Example 1:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color. Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

1
2
3
4

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2:

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Output: [[0,0,0],[0,0,0]] Explanation: The starting pixel is already colored 0, so no changes are made to the image.

1
2
3

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation: The starting pixel is already colored 0, so no changes are made to the image.

Constraints:

m == image.length

n == image[i].length

1 <= m, n <= 50

0 <= image[i][j], color < 2¹⁶

0 <= sr < m

0 <= sc < n

内容

m行×n列で構成される画像であるimageがあります。※実際は2次元配列

imageの各要素には色を表す数値があります。

sr, sc, colorが与えられるので、image[sr][sc]をスタート地点としてflood fillを行ってください。

flood fillは上下左右の4方向に隣接するマスの内、色(値)が同じマスを、colorと同じ色(値)に置き換えることを指します。

flood fillを行った後の画像を返してください。

※問題が良くわからなかったので、自分が読んでわかりやすい書き方に変えました。

問題の意図はつかめると思いますが、訳としては間違っている可能性がかなり高いです。

解答

解答1：Python,DFS

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:

        #深さ優先探索
        def dfs(r,c):
            #nonlocalは関数内関数で、上位の関数にある変数を使いたいときに用いる
            nonlocal rows, cols, color, image

            #行列の範囲外、新色に置換済、置換対象の色ではない場合は何もしない
            if r<0 or c<0 or r>rows-1 or c>cols-1 or image[r][c]==color or image[r][c]!=color_to_change:
                return 
            #上記以外(行列の範囲内で置換対象の色)の場合、新色に置換する
            image[r][c] = color

            #指定された要素の上下左右の要素に対して同様の処理を行う
            dfs(r+1, c)
            dfs(r-1, c)
            dfs(r, c+1)
            dfs(r, c-1)
                
        #行数
        rows = len(image)
        #列数
        cols = len(image[0])
        #置換対象の色
        color_to_change = image[sr][sc]

        #dfs関数を呼び出す
        dfs(sr,sc)

        return image

class Solution:

def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:

#深さ優先探索

def dfs(r,c):

#nonlocalは関数内関数で、上位の関数にある変数を使いたいときに用いる

nonlocal rows, cols, color, image

#行列の範囲外、新色に置換済、置換対象の色ではない場合は何もしない

if r<0 or c<0 or r>rows-1 or c>cols-1 or image[r][c]==color or image[r][c]!=color_to_change:

return

#上記以外(行列の範囲内で置換対象の色)の場合、新色に置換する

image[r][c] = color

#指定された要素の上下左右の要素に対して同様の処理を行う

dfs(r+1, c)

dfs(r-1, c)

dfs(r, c+1)

dfs(r, c-1)

#行数

rows = len(image)

#列数

cols = len(image[0])

#置換対象の色

color_to_change = image[sr][sc]

#dfs関数を呼び出す

dfs(sr,sc)

return image

・イメージ　※image = [[1,1,1],[1,1,0],[1,0,1]] , sc=1 , sr=1 , color=2の場合

中心の1はimage[sr][sc]、つまりスタート位置。上下左右に隣接しており、値が同じマスを2(color)に置き換える。

1は1と隣接しており、色(値)が同じため今回置換対象。

その後、置換した要素からさらに上下左右に同じ操作を繰り返す

1,1,1

1,1,0

1,0,1

↓

1,2,1

2,2,0

1,0,1

↓

2,2,2

2,2,0

2,0,2

解答2：Python,BFS

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]:
        current_color, m, n = image[sr][sc], len(image), len(image[0])

        if current_color != new_color:
            queue = collections.deque([(sr, sc)])
            while queue:
                i, j = queue.popleft()
                image[i][j] = new_color
                for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)) :
                    if 0<=x<m and 0<=y<n and image[x][y] == current_color:
                        queue.append((x, y))

        return image

class Solution:

def floodFill(self, image: List[List[int]], sr: int, sc: int, new_color: int) -> List[List[int]]:

current_color, m, n = image[sr][sc], len(image), len(image[0])

if current_color != new_color:

queue = collections.deque([(sr, sc)])

while queue:

i, j = queue.popleft()

image[i][j] = new_color

for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)) :

if 0<=x<m and 0<=y<n and image[x][y] == current_color:

queue.append((x, y))

return image

解答3：Python, DFS, 英語コメント

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        #Variable "target" has the value of image[sr][sc].
        #Each element which have the value of "target" in image[sr][sc] will be changed its value as the value of "color".
        target = image[sr][sc]
        #Call DFS
        self.DFS(sr,sc,image,color,target)
        #Return image performed a flood fill.
        return image
        
    #DFS
    def DFS(self, sr, sc, image, color,target):
        #When image[sr][sc] is outside of image, DFS does nothing.
        #When the value of image[sr][sc] is same as the color, DFS does nothing.
        #When the value of image[sr][sc] is differnt from the value of target, DFS does nothing.
        if sr<0 or sc<0 or sr>len(image)-1 or sc> len(image[0])-1 or image[sr][sc]!=target or image[sr][sc]==color:
            return 

        
        #change the value of image[sr][sc] to color
        image[sr][sc] = color
        
        #Call DFS 4-directionally(above,below,right,left).
        self.DFS(sr+1,sc,image,color,target)
        self.DFS(sr-1,sc,image,color,target)
        self.DFS(sr,sc+1,image,color,target)
        self.DFS(sr,sc-1,image,color,target)
        
        #Return image after tha value of image[sr][sc] is changed.
        return image

class Solution:

def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:

#Variable "target" has the value of image[sr][sc].

#Each element which have the value of "target" in image[sr][sc] will be changed its value as the value of "color".

target = image[sr][sc]

#Call DFS

self.DFS(sr,sc,image,color,target)

#Return image performed a flood fill.

return image

#DFS

def DFS(self, sr, sc, image, color,target):

#When image[sr][sc] is outside of image, DFS does nothing.

#When the value of image[sr][sc] is same as the color, DFS does nothing.

#When the value of image[sr][sc] is differnt from the value of target, DFS does nothing.

if sr<0 or sc<0 or sr>len(image)-1 or sc> len(image[0])-1 or image[sr][sc]!=target or image[sr][sc]==color:

return

#change the value of image[sr][sc] to color

image[sr][sc] = color

#Call DFS 4-directionally(above,below,right,left).

self.DFS(sr+1,sc,image,color,target)

self.DFS(sr-1,sc,image,color,target)

self.DFS(sr,sc+1,image,color,target)

self.DFS(sr,sc-1,image,color,target)

#Return image after tha value of image[sr][sc] is changed.

return image

面接では英語で入力や実装方法について相談しながら進める必要がありますが、

いきなり英語で話すのは難しいので、まずはコメントアウトに英語を書いています。

表現がわからないときは調べながらでも進められるので練習に良いと思っています。

解答の早さと精度を上げることと並行して、英語で話しながら解答できるようにも練習が必要です。

補足・参考・感想

■メモ

・nonlocalは関数外の変数を使うための宣言なのでglobalと似ている。

globalと異なるのは、関数内関数で使用される点。内側の関数から外側の関数を使いたいときに宣言する。

■類題

200. Number of Islands

695. Max Area of Island

■感想

DFS、BFSを復習しないといけない。関数内関数としてなのか、クラス内のメソッドとしてなのか、どのように実装するかで変わる部分についても把握しておきたい。

前：567. Permutation in String

次：733. Flood Fill

LeetCode 解答・解説記事一覧