スポンサーリンク

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

スポンサーリンク
スポンサーリンク
この記事は約4分で読めます。

学習メモ

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

問題

原文

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 srsc, 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:

Example 2:

 

Constraints:

  • m == image.length
  • n == image[i].length
  • 1 <= m, n <= 50
  • 0 <= image[i][j], color < 216
  • 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

 

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

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

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

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

 

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

 

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

 

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

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

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

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

 

 

補足・参考・感想

■メモ

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

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

■類題

200. Number of Islands

695. Max Area of Island

 

■感想

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

 

前:567. Permutation in String

次:733. Flood Fill

LeetCode 解答・解説記事一覧

コメント