同じ領域のデータを塗りつぶす

はじめに

同じ属性で隣り合ったマスを塗りつぶすアルゴリズムを考えます。

下図のようなint型のデータを持つ2次元配列があったとします。

たとえば、5列目、2行目の"0"を指定した時、
そのマスと隣り合った"0"のマスのすべてを別の値("3")へ置き換える（=塗りつぶす）ことを考えます。

すると下図の結果が得られることを期待値とします。

作戦

スタート地点(5列目,2行目)と、塗りつぶされる値(0)、塗りつぶし後の値(3)はinputされるとします。

スタート地点から上下左右を見て、塗りつぶされる値(0)があるか確認します。

あった場合は、その地点を指定の値(3)で置き換え、またその地点から上下左右を見て、塗りつぶされる値(0)があるか、確認します。

つまり、
"その地点の値を置き換え、さらに上下左右を確認する"
という処理を何度も繰り返し呼び出し続ければよさそうです。(=再帰呼び出し)

サンプルプログラム

• 以下のようなサンプルを組んでみましょう。

sample.cpp

#include <iostream>

// 例題データ準備
const int row = 8;	// 行
const int col = 11;	// 列
int data[row][col] = {
	{	1,	1,	1,	1,	1,	2,	2,	1,	1,	1,	2,	},
	{	2,	0,	1,	1,	0,	0,	0,	0,	2,	0,	1,	},
	{	2,	0,	1,	0,	0,	2,	0,	0,	0,	0,	1,	},
	{	1,	1,	1,	1,	0,	2,	0,	1,	0,	0,	2,	},
	{	1,	1,	0,	1,	0,	0,	1,	0,	1,	0,	1,	},
	{	2,	0,	0,	0,	0,	0,	1,	1,	0,	0,	1,	},
	{	1,	0,	1,	1,	0,	2,	2,	1,	0,	2,	2,	},
	{	1,	1,	1,	2,	2,	1,	1,	1,	1,	1,	1,	},
};

// 指定地点の値を置き換え、さらにその地点から上下左右の値を確認する処理
// x, y = 指定地点の列(x)、行(y)
// checkNo = 塗りつぶされる値
// swapNo = 塗りつぶし後の値
void
fill(int x, int y, int checkNo, int swapNo)
{
	data[y][x] = swapNo;	// 塗りつぶし色へ置き換え

	// 上下左右に"checkNo"の値があるかチェックし、あれば再帰呼び出し
	if (data[y - 1][x] == checkNo) {	// 上
		fill(x, y - 1, checkNo, swapNo);
	}
	if (data[y][x + 1] == checkNo) {	// 右
		fill(x + 1, y, checkNo, swapNo);
	}
	if (data[y + 1][x] == checkNo) {	// 下
		fill(x, y + 1, checkNo, swapNo);
	}
	if (data[y][x - 1] == checkNo) {	// 左
		fill(x - 1, y, checkNo, swapNo);
	}

}

// データを画面に出す関数
void print(char const* str)
{
	std::cout << str << std::endl;

	for (int i = 0; i < row; ++i) {
		for (int j = 0; j < col; ++j) {
			std::cout << data[i][j] << ", ";
		}
		std::cout << std::endl;
	}
}

// メイン
int main()
{
    // 処理前のデータ確認
	print("before");

    // 塗りつぶしを実行！
	// （Input：5行目, 2列目から開始、"0"の値を"3"へ書き換える）
	fill(5, 2, 0, 3);

    // 処理後のデータ確認
	print("after");
}

• 実行結果

before
1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2,
2, 0, 1, 1, 0, 0, 0, 0, 2, 0, 1,
2, 0, 1, 0, 0, 2, 0, 0, 0, 0, 1,
1, 1, 1, 1, 0, 2, 0, 1, 0, 0, 2,
1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1,
2, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1,
1, 0, 1, 1, 0, 2, 2, 1, 0, 2, 2,
1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1,
after
1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2,
2, 0, 1, 1, 3, 3, 3, 3, 2, 3, 1,
2, 0, 1, 3, 3, 3, 3, 3, 3, 3, 1,
1, 1, 1, 1, 3, 2, 3, 1, 3, 3, 2,
1, 1, 3, 1, 3, 3, 1, 0, 1, 3, 1,
2, 3, 3, 3, 3, 3, 1, 1, 3, 3, 1,
1, 3, 1, 1, 3, 2, 2, 1, 3, 2, 2,
1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1,

• 注意
  • 上記サンプルは配列の範囲外アクセスのガード処理とか全然していないので実処理では入れてください。

おわりに

同じ属性で隣り合ったマスを塗りつぶすアルゴリズムをC++で組んでみました。
再帰呼び出しは苦手視しているのですが、うまくハマるとすごく面白いですね。