Flood Fill
画像は整数のグリッドで、各数値は1つのピクセルの色を表します。画像は行のリストとして与えられ、開始ピクセルの行は sr、列は sc、新しい色は color です。開始ピクセルを含む領域を塗り直します。同じ色のピクセルを通って上、下、左、右に移動して開始ピクセルから到達できる、開始ピクセルと同じ色のすべてのピクセルが対象です。塗り直した後の画像を返してください。
関数
- imageinteger-2d-array
- 画像を、1ピクセルにつき1つの数値を含む行のリストとして表します
- srinteger
- 開始ピクセルの行（0から数える）
- scinteger
- 開始ピクセルの列（0から数える）
- colorinteger
- 領域の新しい色
- 戻り値integer-2d-array
- 領域が再描画された後の画像
制約
1 ≤ image.length ≤ 801 ≤ image[i].length ≤ 80- すべての行は同じ長さです。
0 ≤ image[i][j], color ≤ 655350 ≤ sr < image.lengthかつ0 ≤ sc < image[0].length
例
- 入力
- image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
- 出力
- [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
- 説明
- 開始位置には色1があります。その右側の1、左端の列と最下段にある1、そして右下隅の上にある1はすべて開始位置につながっているため、7つすべてが5になります。2つの0は別の色なので、そのままです。
- 入力
- image = [[3, 3, 3], [3, 7, 3], [3, 3, 3]]sr = 1sc = 1color = 7
- 出力
- [[3, 3, 3], [3, 7, 3], [3, 3, 3]]
- 説明
- 開始地点にはすでに色7があるため、その領域を7で塗っても何も変わりません。画像は元の状態に戻り、3の輪は別の色なのでそのままです。
- 入力
- image = [[2, 2, 4, 4], [4, 2, 2, 4], [4, 4, 2, 2]]sr = 2sc = 3color = 9
- 出力
- [[9, 9, 4, 4], [4, 9, 9, 4], [4, 4, 9, 9]]
- 説明
- 2は右下の角から左上へ階段状に並び、それぞれの段が次の段と辺を共有しているため、6つすべてが9に変わります。4は2つの別々の領域に分かれ、色はそのままです。
提出時に隠しテスト+18件
発展問題
角だけで接しているピクセルも連結しているとみなす場合、解答はどのように変わりますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どのピクセルが変化できるのでしょうか？開始ピクセルと同じ色で、その色の経路によって開始ピクセルにつながっているピクセルだけです。
各ピクセルをノードとして扱い、隣り合う辺を共有し、両方が開始色であるピクセル同士をつなぎます。領域は開始位置から到達できるすべての場所なので、どのグラフ探索でも見つけられます。
まだ確認していないピクセルをスタックに保持します。ピクセルをプッシュした時点で塗りつぶすと、塗りつぶされたピクセルは一致しなくなり、再びプッシュされることはありません。まず、新しい色が古い色と等しいかどうかを確認します。
解説
領域とは、グラフの連結した部分です。ピクセルがノードで、開始色の隣り合う2つのピクセルは辺を共有してつながっています。指定されたピクセルから始め、その色のピクセルだけをたどる探索なら、領域全体を見つけられます。注意すべき点は、新しい色が元の色と同じ場合と、再帰探索を破綻させるほど長く曲がりくねった領域です。
再帰的深さ優先探索
正しいが、最大のテストでは終わらない
考え方
paint(r, c)という関数を書き、次の小さな処理を行います。(r, c)が画像内にあり、まだ古い色なら、そのピクセルを新しい色で塗り、4つの隣接ピクセルに対して自分自身を呼び出します。開始ピクセルで1回呼び出すだけで、領域全体に色が広がります。領域内のすべてのピクセルは古い色のピクセルをたどる経路で開始地点につながっており、呼び出しがその経路をたどるためです。
4つの呼び出しを行う前にピクセルを塗ることで、色がぐるぐると広がるのを防ぎます。隣接ピクセルから塗り済みのピクセルに戻って呼び出されても、色が一致しなくなっているため、その呼び出しはすぐに戻ります。これは新しい色が古い色と異なる場合にのみ機能するため、最初にそれを確認し、同じなら画像を変更せずに返します。
処理量は O(m × n) ですが、弱点は呼び出しスタックです。再帰の深さは、たどっている経路の長さと同じになります。80 × 80 の画像を通る幅1ピクセルの蛇行した経路は約3,200ピクセルの長さなので、呼び出しは約3,200段ネストします。Pythonはデフォルトで1,000回で停止してエラーを発生させるため、この方法では最大のテストを完了できません。他の言語ではより深い呼び出しが可能ですが、画像がさらに大きくなれば、やはり呼び出しスタックを使い果たしてしまいます。
アルゴリズム
old = image[sr][sc]を読み取ります。oldがcolorと等しい場合は、画像を返します。paint(r, c)を定義します。(r, c)が画像の範囲外の場合、またはその色がoldでない場合は戻ります。- それ以外の場合は
image[r][c] = colorを設定し、上、下、左、右のピクセルに対してpaintを呼び出します。 paint(sr, sc)を呼び出し、画像を返します。
def floodFill(image, sr, sc, color):
old = image[sr][sc]
if old == color:
return image
rows, cols = len(image), len(image[0])
def paint(r, c):
# Stop outside the image and at any pixel that is not the old color.
if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
return
image[r][c] = color
paint(r + 1, c)
paint(r - 1, c)
paint(r, c + 1)
paint(r, c - 1)
paint(sr, sc)
return image明示的なスタックを使った深さ優先探索
考え方
同じ探索を行いますが、訪問するピクセルはコールスタックではなく、自分で用意したスタックに保持します。開始ピクセルを塗り、スタックにプッシュします。ピクセルをポップし、その4つの隣接ピクセルを調べます。画像内にあり、まだ古い色のままの隣接ピクセルは、それぞれ塗ってプッシュします。スタックが空になれば、領域全体を塗り終えています。
ピクセルはポップするときではなく、プッシュするときに塗ります。塗られたピクセルはもう古い色ではないため、色のチェックを訪問済みかどうかのチェックとして兼用できます。ピクセルがスタックに2回入ることはなく、別途マーク用のグリッドを用意する必要もありません。再帰版と同様に、新しい色は古い色と異なる必要があるため、両者が等しい場合は画像を変更せずに返します。
領域内の各ピクセルは1回プッシュされ、4つの隣接ピクセルを調べるため、時間計算量は O(m × n) です。スタックに保持されるのは最大でも領域内のピクセル数です。スタックは通常のメモリ上にあるため、再帰版ではコールスタックがあふれた、曲がりくねった3,200ピクセルの領域でも問題ありません。
アルゴリズム
old = image[sr][sc]を読み取ります。oldがcolorと等しい場合は、画像を返します。(sr, sc)を塗り、スタックに積みます。- ピクセルを取り出し、その4近傍を確認します。
- 画像内にある各近傍の色が
oldであれば、それを塗ってスタックに積みます。 - スタックが空になったら、画像を返します。
def floodFill(image, sr, sc, color):
old = image[sr][sc]
# Painting a region its own color changes nothing. Returning here also
# stops the search from pushing the same cells forever.
if old == color:
return image
rows, cols = len(image), len(image[0])
image[sr][sc] = color
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
# Paint on push: a painted cell no longer matches old,
# so it can never be pushed twice.
image[nr][nc] = color
stack.append((nr, nc))
return image
落とし穴と境界ケース
誤答の多くは、色が同じ場合の処理、画像の範囲外へのアクセス、または大きな領域での再帰が原因です。
colorが開始時の色と等しい場合を忘れる。塗り替えても何も変わらないため、色を訪問済みの印として使う探索では、同じピクセルが際限なく追加されます。- 塗り替えた後に
image[sr][sc]を読み取る。先に古い色を保存しないと、すべての隣接ピクセルを新しい色と比較することになります。 - 斜めの隣接ピクセルを数える。角だけが接しているピクセル同士はつながっていません。
- 隣接ピクセルが画像内にあるかを確認する前に、その色を調べる。まず
0 ≤ row < rowsと0 ≤ col < colsを確認します。 - 大きな画像で再帰を使う。80 × 80の画像を通る幅1ピクセルの経路は約3,200ピクセルの長さになり、Pythonの再帰上限を超える深さに達することがあります。
- 画像全体にある古い色のピクセルをすべて塗り替える。開始地点から切り離されている同じ色のピクセルは、その色のままにしておく必要があります。
よくある質問4
Flood Fill の時間計算量はどのくらいですか？
m 行 n 列の画像では O(m × n) です。領域内の各ピクセルはスタックに一度プッシュされ、4 つの隣接ピクセルを調べます。また、領域外のピクセルは隣接ピクセルとして調べられるだけです。画像全体が 1 つの領域である場合、スタックには最大 m × n 個のピクセルを保持できます。
BFSとDFSのどちらをFlood Fillに使うべきでしょうか？
どちらでも機能し、どちらも O(m × n) の時間がかかります。訪問する順序にかかわらず領域は同じなので、キュー（幅優先）でもスタック（深さ優先）でも同じピクセルが塗られます。使っている言語で書くのが短い方を選び、大きな画像では再帰を避けましょう。
新しい色が元の色と同じ場合、Flood Fill のループが止まらなくなるのはなぜですか？
一般的な解決方法では、「まだ古い色のまま」を「まだ訪問していない」として扱います。新しい色が古い色と同じ場合、ピクセルを塗っても変化しないため、その隣接ピクセルが再びスタックに追加され、探索が終わりません。最初にこのケースを確認して画像を返すことで修正でき、変更されていない画像が正しい答えです。
Flood Fillは再帰的に解けますか？
はい、ピクセルを塗り、古い色の隣接ピクセルごとに自分自身を呼び出す関数で正しく処理できます。注意点は深さです。再帰の深さは探索がたどる最長経路と同じになり、曲がりくねった領域では呼び出しが数千回になることがあります。明示的なスタックを使えば、その制限なしに同じ処理ができます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def floodFill(image, sr, sc, color):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]] sr = 0 sc = 0 color = 5
期待値
[[5, 5, 0], [5, 0, 5], [5, 5, 5]]