フラッドフィルアルゴリズム - 開発者ドキュメント

1. 概要

このチュートリアルでは、シードフィルとも呼ばれるフラッドフィルアルゴリズムについて説明します。

まず、アルゴリズムを定義し、それを説明する例を示します。

次に、このアルゴリズムへの2つのアプローチについて説明します。最後に、それのいくつかの有用な使用法を示します。

塗りつぶしは、多次元配列内の特定のセルに接続されている領域を決定するアルゴリズムです。

ピクセルの2D配列として表現できるカラフルな画像があるとします。この2D配列の各ピクセルには色があります。私たちの仕事は、特定の色を持つ領域の色を新しい色に変更することです。

最初に、フラッドフィルアルゴリズムは2つのパラメータを取ります。

簡単にするために、各セルの隣接セルは、セルの上部、下部、左側、および右側のセルであると見なします。また、セルを接続領域の一部と見なすには、最初のセルと同じ色である必要があります。

理解を深めるために例を確認してみましょう。次の2D配列があるとします。

与えられたとしましょう。ご覧のとおり、セルの色は青です。したがって、同じ色を持つ接続されているすべてのセルの色を：に変更します。

最初のセルの隣接セルに色を付けるだけではないことに注意してください。対照的に、最初のセルの隣接セルを考慮し、新しく検出された各セルの隣接セルを見つけ続けます。この操作は、新しい隣接セルが検出されなくなるまで続行されます。

さらに、左下のセルの最後の色はまだ青色です。その理由は、最初のセルを含む接続領域の一部ではないためです。

ここでの主なアイデアは、 BFS （幅優先探索）アルゴリズムを使用して、の隣接する4つのセルに移動し、それらの色を変更することです。そのために、実装を3つのステップに分割します。

まず、特定のセルの移動が有効かどうかを判断するのに役立つ関数を作成します。次に、BFSアプローチを実装します。最後に、実装を改善して、よりクリーンで短くする方法を見ていきます。

実装を見てみましょう：

この関数は、移動先のセルが有効かどうかを示します。次の条件が当てはまる場合に有効です。

BFSアプローチの最初の実装を見てください。

最初に、BFSトラバーサル中にセルを格納するための空のキューを宣言します。また、ソースセルの初期色を表す変数を宣言します。

次に、キューが空でない限り、複数のステップを実行します。各ステップで、キューの先頭に配置されているセルを取得し、キューから削除し、色をに変更して、訪問済みセルとしてマークします。その後、隣接する有効な隣接セルをキューに追加します。

最後に、ループが終了すると、最初のセルのすべての領域が訪問済みとしてマークされ、新しい色になります。

ご覧のとおり、実装は少し面倒です。したがって、わかりやすくするために、1行のコードで隣接するすべてのセルに移動するのに役立つ2つの遷移配列を宣言します。

ここでの遷移配列は、現在のセルから隣接するセルに移動するために必要なオフセットを提供します。たとえば、遷移により、現在のセルの左側にあるセルが得られます。

さらに、セルをキューに追加する前に各セルを変更するのではなく、キューからセルを取得するときにセルの色を変更できます。

このアプローチの複雑さはBFSの複雑さと同じです。です。ここで、は2D配列の行数、は列数です。この複雑さの背後にある理由は、元のBFSの複雑さに似ているためです。ここで、は頂点の数であり、はエッジの数です。

この場合、各セルには4つの隣接するセルがあるため、頂点の数は、であり、エッジの数は）です。

DFS （深さ優先探索）アルゴリズムでは、前のBFSアプローチと同じ概念を適用して、の4つの隣接するセルにトラバースし、それらの色を変更します。さらに、セクション3.1で定義された関数と、遷移配列を使用してネイバーを訪問する拡張バージョンを使用します。

実装を見てみましょう：

最初に、前のアプローチと同じ2つの遷移配列を宣言します。

次に、関数に入るたびに、現在のセルを訪問済みとしてマークします。また、現在のセルの色をに変更します。

次に、隣接する4つのセルを繰り返し処理します。それぞれについて、移動が有効かどうかを確認します。その場合、そのセルで関数を再帰的に呼び出します。

最後に、ソースセルに接続され、ソースセルと同じ色のすべての領域が。で色付けされます。

このアプローチの複雑さは、DFSの複雑さと同じです。です。ここで、は2D配列の行数、は列数です。この複雑さの背後にある理由は、セクション3.3で説明した理由と同じです。

フラッドフィルアルゴリズムを使用する必要があるいくつかのケースについて説明しましょう。

これは、ペイントプログラムのバケツ塗りつぶしツールで使用され、接続された同じ色の領域を異なる色で塗りつぶします。画像の1ピクセルをクリックするだけで、クリックしたセルに関連する接続領域のすべてのセルの色が新しいセルに変更されていることがわかります。
囲碁や掃海艇などのゲームで、どの駒をクリアするかを決定します。地雷も番号もないグリッドのセルをクリックしたとします。この場合、ゲームは空で同じ接続領域内にあるすべてのセルを開きます。ただし、この場合、数値を含むセルに到達したときに停止するアルゴリズムの更新が1つあります。
2つのセルが同じ接続領域内にあるかどうかを確認します。この使用法では、事前に接続されたエリアごとに一意の識別子を与えることができます。後で、グリッド内の2つのセルに関するクエリを受け取ったときに、それぞれの識別子をチェックして、それらが一致するかどうかを確認するだけで済みます。

この記事では、フラッドフィルアルゴリズムを紹介しました。一般的な考え方を説明し、問題を解決するための2つのアプローチについて説明しました。最後に、実際の問題でのアルゴリズムの公正な使用法を提供しました。