フラッドフィルアルゴリズムとは？C++でペイントの塗りつぶし（fill）機能を実装する方法

問題概要

この問題では、2次元画面を表す2次元配列と、色を塗りたいピクセルの座標、そして新しい色が与えられます。私たちのタスクは、指定されたピクセルと、そのピクセルと同じ色を持つすべての隣接ピクセルを新しい色で塗りつぶすプログラムを作成することです。

これは、お絵かきソフト（ペイント）でバケツツールを使う操作に相当します。好きな色を選び、ブラシで目的のピクセルをクリックすると、つながっている同じ色の領域全体が一気に塗り替えられるのです。

具体例で問題を理解しよう

入力：Screen[][] =
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, Y, Y, Y, Y, B, W, B},
{B, W, W, Y, Y, B, W, B},
{B, W, W, Y, Y, Y, Y, B},
{W, B, W, W, W, Y, W, W},
{W, W, B, B, W, Y, Y, W}};
X = 5, Y = 5, newColor = R

出力：
{{W, W, B, W, W, W, W, W},
{W, W, W, W, W, W, B, B},
{W, B, B, W, W, B, W, W},
{W, R, R, R, R, B, W, B},
{B, W, W, R, R, B, W, B},
{B, W, W, R, R, R, R, B},
{W, B, W, W, W, R, W, W},
{W, W, B, B, W, R, R, W}};

座標(5, 5)のピクセルは元々Y（黄色）なので、それにつながっているYの領域全体がR（赤）に塗り替えられているのが分かります。

フラッドフィルアルゴリズムの仕組み

フラッドフィル（Flood Fill）アルゴリズムでは、対象のピクセルが現在の「元の色」と一致している場合にのみ、新しい色で塗りつぶします。元の色と異なるピクセルは塗りつぶされません。1つのピクセルを塗った後は、その上下左右の4方向のピクセルに対して同じ処理を再帰的に適用していきます。

解法アプローチ：再帰による実装

この問題を解く最も一般的な方法は、再帰的なアプローチです。処理の手順は以下の通りです。

1. まず最初に塗りつぶすべきピクセルを見つけます。
2. その上下左右の4つの隣接ピクセルを確認します。
3. 隣接ピクセルが開始ピクセルと同じ色であれば、新しい色に置き換え、さらにその隣接ピクセルに対して同じ処理を繰り返します。
4. 隣接ピクセルが異なる色の場合は、そのまま何もせずスキップします。
5. 開始ピクセルと同じ色を持つすべての隣接ピクセルが塗り終わるまで手順を続け、完了したらアルゴリズムを停止します。

C++での実装例

以下は、このソリューションの動作を示すC++プログラムです。

#include<iostream>
using namespace std;
#define M 8
#define N 8

void fillColorAdj(char screen[][N], int x, int y, char oldColor, char color){
    if (x < 0 || x >= M || y < 0 || y >= N)
        return;
    if (screen[x][y] != oldColor)
        return;
    if (screen[x][y] == color)
        return;
    screen[x][y] = color;

    fillColorAdj(screen, x+1, y, oldColor, color);
    fillColorAdj(screen, x-1, y, oldColor, color);
    fillColorAdj(screen, x, y+1, oldColor, color);
    fillColorAdj(screen, x, y-1, oldColor, color);
}

void fillColor(char screen[][N], int x, int y, char color){
    char oldColor = screen[x][y];
    if(oldColor==color) return;
    fillColorAdj(screen, x, y, oldColor, color);
}

int main(){
    char screen[M][N] = {{'W', 'W', 'B', 'W', 'W', 'W', 'W', 'W'},
        {'W', 'W', 'W', 'W', 'W', 'W', 'B', 'B'},
        {'W', 'B', 'B', 'W', 'W', 'B', 'W', 'W'},
        {'W', 'Y', 'Y', 'Y', 'Y', 'B', 'W', 'B'},
        {'B', 'W', 'W', 'Y', 'Y', 'B', 'W', 'B'},
        {'B', 'W', 'W', 'Y', 'Y', 'Y', 'Y', 'B'},
        {'W', 'B', 'W', 'W', 'W', 'Y', 'W', 'W'},
        {'W', 'W', 'B', 'B', 'W', 'Y', 'Y', 'W'}};
    int x = 5, y = 5;
    char color = 'R';

    cout<<"The initial screen cordinates are : \n";
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++)
            cout<<screen[i][j]<<"\t";
        cout<<endl;
    }

    fillColor(screen, x, y, color);
    cout<<"\nThe screen cordinates after coloring are : \n";
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++)
            cout<<screen[i][j]<<"\t";
        cout<<endl;
    }
}

出力結果

The initial screen cordinates are :
W   W   B   W   W   W   W   W
W   W   W   W   W   W   B   B
W   B   B   W   W   B   W   W
W   Y   Y   Y   Y   B   W   B
B   W   W   Y   Y   B   W   B
B   W   W   Y   Y   Y   Y   B
W   B   W   W   W   Y   W   W
W   W   B   B   W   Y   Y   W

The screen cordinates after coloring are :
W   W   B   W   W   W   W   W
W   W   W   W   W   W   B   B
W   B   B   W   W   B   W   W
W   R   R   R   R   B   W   B
B   W   W   R   R   B   W   B
B   W   W   R   R   R   R   B
W   B   W   W   W   R   W   W
W   W   B   B   W   R   R   W

このように、フラッドフィルアルゴリズムを使えば、ペイントアプリの塗りつぶし機能と同じ動作を簡単に実装できます。再帰呼び出しが画面の範囲外や異なる色のピクセルに到達した時点で自動的に終了するため、つながった同色領域だけが効率よく塗り替えられる点がポイントです。