★関数（再帰呼び出し４）★

さて、再帰呼び出しの使い道について、実用的とは言えませんが、少し趣向を変えてみましょう。

今回の題材は「画像の塗りつぶし」です。

ペイントツールなどで、閉ざされた領域をある色で塗りつぶすことをイメージしてみてください。

例えば、こんな絵を、

塗りつぶしツールを使って、

のように塗りつぶすイメージです。

ただ、２Ｄグラフィックは扱えませんので、あくまでもコンソールで作ります。

迷路などで使った２次元配列を利用して、疑似的な画像を作ります。

＜画像イメージ＞

□□□□□□□□□□□
□□□□□□□□□□□
□□□□□□□□□□□
□□■□□□□□■□□
□□□■□□□■□□□
□□■■■■■■■□□
□■■□■■■□■■□
■■■■■■■■■■■
■□■■■■■■■□■
■□■□□□□□■□■
□□□■■□■■□□□

まずはこれを作りましょう。

□と■を使いますので、配列内では０と１で表現することにしましょう。

まずは必要なものを考えます。

２次元配列の縦は１１マス、横も１１マスです。

これは#defineで定義しましょう。

□を０、■を１で表現しますが、WHITEとBLACKという定数をenumで用意します。

２次元配列fieldを用意し、初期値を入れて表示するところまで作りましょう。

表示にはShowField関数を作成し、２次元配列を渡して表示します。

<sample program 150-01>

#include <stdio.h>

#define ROW 11
#define COL 11

enum {
    WHITE,
    BLACK,
};

void ShowField(const int field[ROW][COL]);

int main(void)
{
    int field[ROW][COL] = {
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0 },
    };

    ShowField(field);

    return 0;
}


void ShowField(const int field[ROW][COL])
{
    int i;
    int j;

    for (i = 0; i < ROW; i++) {
        for (j = 0; j < COL; j++) {
            switch (field[i][j]) {
            case WHITE:
                printf("□");
                break;
            case BLACK:
                printf("■");
                break;
            }
        }
        printf("\n");
    }

    printf("\n");
}

<実行結果>

□□□□□□□□□□□
□□□□□□□□□□□
□□□□□□□□□□□
□□■□□□□□■□□
□□□■□□□■□□□
□□■■■■■■■□□
□■■□■■■□■■□
■■■■■■■■■■■
■□■■■■■■■□■
■□■□□□□□■□■
□□□■■□■■□□□
続行するには何かキーを押してください・・・

画像の準備は出来ました。

コンソールではマウスが使えませんので、どの領域を塗りつぶすか座標を入力することで選択します。

そのために、以前作った「宝探し」のように座標を表示しましょう。

<sample program 150-02>

#include <stdio.h>

#define ROW 11
#define COL 11

enum {
    WHITE,
    BLACK,
};

void ShowField(const int field[ROW][COL]);

int main(void)
{
    int field[ROW][COL] = {
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0 },
    };

    ShowField(field);

    return 0;
}


void ShowField(const int field[ROW][COL])
{
    int i;
    int j;

    printf("   0 1 2 3 4 5 6 7 8 9 10\n");

    for (i = 0; i < ROW; i++) {

        printf("%2d ", i);

        for (j = 0; j < COL; j++) {
            switch (field[i][j]) {
            case WHITE:
                printf("□");
                break;
            case BLACK:
                printf("■");
                break;
            }
        }
        printf("\n");
    }

    printf("\n");
}

<実行結果>

   0 1 2 3 4 5 6 7 8 9 10
 0 □□□□□□□□□□□
 1 □□□□□□□□□□□
 2 □□□□□□□□□□□
 3 □□■□□□□□■□□
 4 □□□■□□□■□□□
 5 □□■■■■■■■□□
 6 □■■□■■■□■■□
 7 ■■■■■■■■■■■
 8 ■□■■■■■■■□■
 9 ■□■□□□□□■□■
10 □□□■■□■■□□□
続行するには何かキーを押してください・・・

次に塗りつぶす座標を入力出来るように、変数ｘとｙを作り、入力出来るようにします。

<sample program 150-03>

#include <stdio.h>

#define ROW 11
#define COL 11

enum {
    WHITE,
    BLACK,
};

void ShowField(const int field[ROW][COL]);

int main(void)
{
    int x;
    int y;

    int field[ROW][COL] = {
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0 },
    };

    ShowField(field);

    do {
        printf("Input X:");
        scanf("%d", &x);
    } while (x < 0 || x >= COL);

    do {
        printf("Input Y:");
        scanf("%d", &y);
    } while (y < 0 || y >= ROW);

    return 0;
}


void ShowField(const int field[ROW][COL])
{
    int i;
    int j;

    printf("   0 1 2 3 4 5 6 7 8 9 10\n");

    for (i = 0; i < ROW; i++) {

        printf("%2d ", i);

        for (j = 0; j < COL; j++) {
            switch (field[i][j]) {
            case WHITE:
                printf("□");
                break;
            case BLACK:
                printf("■");
                break;
            }
        }
        printf("\n");
    }

    printf("\n");
}

<実行結果>

   0 1 2 3 4 5 6 7 8 9 10
 0 □□□□□□□□□□□
 1 □□□□□□□□□□□
 2 □□□□□□□□□□□
 3 □□■□□□□□■□□
 4 □□□■□□□■□□□
 5 □□■■■■■■■□□
 6 □■■□■■■□■■□
 7 ■■■■■■■■■■■
 8 ■□■■■■■■■□■
 9 ■□■□□□□□■□■
10 □□□■■□■■□□□

Input X:5
Input Y:0
続行するには何かキーを押してください・・・

さて、ここからが本番です。

指定した座標を含む領域を塗りつぶすプログラムを考えます。

今のところ、色は白黒しか使えませんので、図形の「☆」で塗りつぶすことにします。

仮に、「☆」を赤（RED）としましょう。

enumに追加するのと、表示のところにも追加します。

<sample program 150-04>

#include <stdio.h>

#define ROW 11
#define COL 11

enum {
    WHITE,
    BLACK,
    RED,
};

void ShowField(const int field[ROW][COL]);

int main(void)
{
    int x;
    int y;

    int field[ROW][COL] = {
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0 },
    };

    ShowField(field);

    do {
        printf("Input X:");
        scanf("%d", &x);
    } while (x < 0 || x >= COL);

    do {
        printf("Input Y:");
        scanf("%d", &y);
    } while (y < 0 || y >= ROW);

    return 0;
}


void ShowField(const int field[ROW][COL])
{
    int i;
    int j;

    printf("   0 1 2 3 4 5 6 7 8 9 10\n");

    for (i = 0; i < ROW; i++) {

        printf("%2d ", i);

        for (j = 0; j < COL; j++) {
            switch (field[i][j]) {
            case WHITE:
                printf("□");
                break;
            case BLACK:
                printf("■");
                break;
            case RED:
                printf("☆");
                break;
            }
        }
        printf("\n");
    }

    printf("\n");
}

<実行結果>

   0 1 2 3 4 5 6 7 8 9 10
 0 □□□□□□□□□□□
 1 □□□□□□□□□□□
 2 □□□□□□□□□□□
 3 □□■□□□□□■□□
 4 □□□■□□□■□□□
 5 □□■■■■■■■□□
 6 □■■□■■■□■■□
 7 ■■■■■■■■■■■
 8 ■□■■■■■■■□■
 9 ■□■□□□□□■□■
10 □□□■■□■■□□□

Input X:0
Input Y:10
続行するには何かキーを押してください・・・

最後に再帰呼び出し用の関数を考えます。

塗りつぶすために必要なデータは以下の通りです。

配列     field

座標     x, y

元の色   sourColor 選択した座標の色情報

新しい色 destColor 今回は赤（RED）

これらを引数として関数Fillを作成します。

＜プロトタイプ宣言＞

void Fill(int field[ROW][COL], const int x, const int y, const int sourColor, const int destColor);

長いですが、必要なデータです。

  field内で指定された座標（x,y）の色（sourColor）を新しい色（destColor）で塗りつぶします。

いきなり関数を書くのではなく、まずは流れを書いてみます。

＜再帰呼び出し用：Fill関数＞

  １．field内の指定された座標を新しい色で書き換えます。

  ２．指定された座標の１つ上のマスを調べて、sourColorと同じ色であれば、座標を変えてFill関数を呼び出します。

  ３．指定された座標の１つ右のマスを調べて、sourColorと同じ色であれば、座標を変えてFill関数を呼び出します。

  ４．指定された座標の１つ下のマスを調べて、sourColorと同じ色であれば、座標を変えてFill関数を呼び出します。

  ５．指定された座標の１つ左のマスを調べて、sourColorと同じ色であれば、座標を変えてFill関数を呼び出します。

隣り合ったマス（上下左右）の色がsourColorと同じであれば、自分自身を呼び出すのです。

１は簡単に、

field[y][x] = destColor;

これでＯＫです。

２以降は少し考えなければなりません。

１つ上のマスを見てsourColorと同じかどうか調べるプログラムは、

if (field[y - 1][x] == sourColor)

で作れますが、座標によってはマズい状況になります。

もし、指定された座標が画像の左上（x = 0, y = 0）であった場合、

field[y - 1][x]

は

field[0 - 1][0]

となり、

field[-1][0]

になるため、配列の領域を超えてしまいます。

端の座標を選択することも考慮し、次のようにすれば大丈夫です。

if (y - 1 > 0) {
    if(field[y - 1][x] == sourColor) {

    }
}

座標を変えてFill関数を呼び出すというのは、１つ上の色がsourColorと同じであれば、１つ上のマスを塗りつぶすため、１つ上の座標を指定して自分自身を呼び出します。

if (y - 1 > 0) {
    if(field[y - 1][x] == sourColor) {
        Fill(field, x, y - 1, sourColor, destColor);
    }
}

これで、１つ上の座標を使ってFill関数を呼び出せます。

それでは、完成形を作りましょう。

<sample program 150-05>

#include <stdio.h>

#define ROW 11
#define COL 11

enum {
    WHITE,
    BLACK,
    RED,
};

void ShowField(const int field[ROW][COL]);

void Fill(int field[ROW][COL], const int x, const int y, const int sourColor, const int destColor);

int main(void)
{
    int x;
    int y;

    int field[ROW][COL] = {
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0 },
        { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 },
        { 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 },
        { 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 },
        { 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0 },
    };

    ShowField(field);

    do {
        printf("Input X:");
        scanf("%d", &x);
    } while (x < 0 || x >= COL);

    do {
        printf("Input Y:");
        scanf("%d", &y);
    } while (y < 0 || y >= ROW);

    Fill(field, x, y, field[y][x], RED);

    ShowField(field);

    return 0;
}


void ShowField(const int field[ROW][COL])
{
    int i;
    int j;

    printf("   0 1 2 3 4 5 6 7 8 9 10\n");

    for (i = 0; i < ROW; i++) {

        printf("%2d ", i);

        for (j = 0; j < COL; j++) {
            switch (field[i][j]) {
            case WHITE:
                printf("□");
                break;
            case BLACK:
                printf("■");
                break;
            case RED:
                printf("☆");
                break;
            }
        }
        printf("\n");
    }

    printf("\n");
}

void Fill(int field[ROW][COL], const int x, const int y, const int sourColor, const int destColor)
{
    field[y][x] = destColor;

    if (y - 1 >= 0) {
        if (field[y - 1][x] == sourColor) {
            Fill(field, x, y - 1, sourColor, destColor);
        }
    }

    if (x + 1 < COL) {
        if (field[y][x + 1] == sourColor) {
            Fill(field, x + 1, y, sourColor, destColor);
        }
    }

    if (y + 1 < ROW) {
        if (field[y + 1][x] == sourColor) {
            Fill(field, x, y + 1, sourColor, destColor);
        }
    }

    if (x - 1 >= 0) {
        if (field[y][x - 1] == sourColor) {
            Fill(field, x - 1, y, sourColor, destColor);
        }
    }
}

<実行結果>

   0 1 2 3 4 5 6 7 8 9 10
 0 □□□□□□□□□□□
 1 □□□□□□□□□□□
 2 □□□□□□□□□□□
 3 □□■□□□□□■□□
 4 □□□■□□□■□□□
 5 □□■■■■■■■□□
 6 □■■□■■■□■■□
 7 ■■■■■■■■■■■
 8 ■□■■■■■■■□■
 9 ■□■□□□□□■□■
10 □□□■■□■■□□□

Input X:0
Input Y:10

   0 1 2 3 4 5 6 7 8 9 10
 0 □□□□□□□□□□□
 1 □□□□□□□□□□□
 2 □□□□□□□□□□□
 3 □□■□□□□□■□□
 4 □□□■□□□■□□□
 5 □□■■■■■■■□□
 6 □■■□■■■□■■□
 7 ■■■■■■■■■■■
 8 ■☆■■■■■■■□■
 9 ■☆■□□□□□■□■
10 ☆☆☆■■□■■□□□
続行するには何かキーを押してください・・・

※色々な座標を指定して試してみてください。

最後に、どのように動作しているのか順を追って見てみましょう。

まず、最初の状態を数値で表したのが↓です。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 0 1 0 0 0 0 0 1 0 1
 0 0 0 1 1 0 1 1 0 0 0

指定した座標が、

  Ｘ　０
  Ｙ　１０

だとすると起点はここです。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 0 1 0 0 0 0 0 1 0 1
 0 0 0 1 1 0 1 1 0 0 0

再帰関数の中で、まずは起点に新しい色を入れていますから、

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 0 1 0 0 0 0 0 1 0 1
 2 0 0 1 1 0 1 1 0 0 0

こうなります。

関数内で次につながっているマスをチェックする順番は「上右下左」の順ですから、次は１つ上をチェックします。

１つ上のマスには「１」が入っていますので、無視されます。

次に１つ右のマスを調べると、塗り替えるべき色なので、起点を１つ右に移し自分自身を呼び出します。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 0 1 0 0 0 0 0 1 0 1
 2 0 0 1 1 0 1 1 0 0 0

ここにも新しい色を入れます。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 0 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

ここからまた「上右下左」の順番にチェックしていきます。

１つ上は塗り替える色なので、また起点を変えて自分自身を呼び出します。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 0 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

新しい起点を塗りつぶします。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

起点が変わったので、また「上右下左」の順でチェックします。

１つ上は塗り替えるべき色ですから、起点を変えて自分自身を呼び出します。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 0 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

新しい起点を塗りつぶします。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 2 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

ここから「上右下左」をチェックしますが、どこも塗り替えるべき色ではありません。

塗り替えるマスが無いので、この関数は終わり１つ前の関数に戻ります。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 2 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

１つ前の関数の起点は↑です。

すでに「上」はチェック済みですから「右下左」をチェックします。

ここでも塗り替えるべき色はありませんので、また１つ前の関数に戻ります。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 2 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

この起点も「上」のみチェック済みですから「右下左」とチェックします。

右が塗り替えるべき色ですから、起点を変えて自分自身を呼び出します。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 2 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 0 1 1 0 1 1 0 0 0

新しい起点を塗りつぶします。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 2 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 2 1 1 0 1 1 0 0 0

ここでも「上右下左」をチェックしますが、塗り替えるべき色はありませんので、１つ前の関数に戻ります。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 2 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 2 1 1 0 1 1 0 0 0

この起点は「上右」のみチェック済みですから「下左」をチェックします。

塗り替えるべき色はありませんので、１つ前の関数に戻ります。

 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 1 0 0
 0 0 0 1 0 0 0 1 0 0 0
 0 0 1 1 1 1 1 1 1 0 0
 0 1 1 0 1 1 1 0 1 1 0
 1 1 1 1 1 1 1 1 1 1 1
 1 2 1 1 1 1 1 1 1 0 1
 1 2 1 0 0 0 0 0 1 0 1
 2 2 2 1 1 0 1 1 0 0 0

最初の起点に戻りました。

最初の起点は「上右」のみチェック済みですから「下左」をチェックします。

塗り替えるべき色はありませんので、main関数に戻って終わりです。

最初に実用的でないと書きました。

小さい領域であれば問題無いのですが、領域が大きくなれば途中で止まってしまいます。

次回は、人気ゲームの一部を題材に再帰を使ったプログラムを作ってみましょう。

次へ

戻る

目次へ