２次元配列のマスを数える方法を教えてください！！

質問

C++において、２次元配列の要素で上下左右に連続して塗り潰されている集まりをカウントする方法を教えてください！！
10*10の２次元配列を用意して、上下左右に連続して塗り潰されている集まりを関数の再帰処理を用いてカウントするプログラムを作りたいのですがわかりません。

問題例
◇◆◇◇◇◆◇◆
◆◆◇◆◇◇◇◆
◇◇◇◆◆◆◇◆
この場合集まりは4です!

配列はstring型で多バイトの文字をカウントします。

回答お願いします！！

回答No.2

chie65535

ループ文をコピペしてから変数名と判定式を直すの忘れた。

誤
　　for (y=1;y<=3;y++) {
　　　　for (x=1;y<=3;y++) {

正
　　for (y=1;y<=3;y++) {
　　　　for (x=1;x<=8;x++) {

実際、こういうバグは良くやる(^^;

回答No.1

chie65535

元よりも一回り大きいint型の２次元配列を用意して

◇◆◇◇◇◆◇◆
◆◆◇◆◇◇◇◆
◇◇◇◆◆◆◇◆

の各文字を数値に変換して

-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,　0,-1,-1,-1, 0,-1,　0,-1
-1,　0,　0,-1, 0,-1,-1,-1,　0,-1
-1,-1,-1,-1,　0, 0,　0,-1,　0,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1

のようなデータを作る。

一回り大きくなっていて、周囲がすべて-1になっている事に注意しよう。

で、こういうデータが用意できたら「集まり番号」を「0」に初期化しておく。

次に、配列の[1][1]～[1][8]、[2][1]～[2][8]、[3][1]～[3][8]の順でスキャンしていく。

void main(void)
{
　　int 集まり番号=0;
　　int y,x;
　　文字列をintの二次元配列に変換する関数();
　　for (y=1;y<=3;y++) {
　　　　for (x=1;y<=3;y++) {
　　　　　　if ( ! 二次元配列[yの位置][xの位置]) {
　　　　　　　　trace(y,x,++集まり番号);
　　　　　　}
　　　　}
　　}
　　printf("集まりの個数は%d個です\n",集まり番号);
}

最初に[1][2]の所（以下の★に相当する所）で、配列要素が0になっているのを見つけたら、集まり番号をインクリメントしてから、追跡ルーチンを呼び出す。

◇★◇◇◇◆◇◆
◆◆◇◆◇◇◇◆
◇◇◇◆◆◆◇◆

追跡ルーチンは

void trace(int yの位置,int xの位置,int 集まり番号)
{
　　if ( ! 二次元配列[yの位置][xの位置]) {
　　　　trace(int yの位置-1,int xの位置,int 集まり番号);
　　　　trace(int yの位置+1,int xの位置,int 集まり番号);
　　　　trace(int yの位置,int xの位置-1,int 集まり番号);
　　　　trace(int yの位置,int xの位置+1,int 集まり番号);
　　　　二次元配列[yの位置][xの位置] = 集まり番号;
　　}
}

って感じ。

メインルーチンの二重ループが終了した時点で、二次元配列の中身は

-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
-1,-1,　1,-1,-1,-1, 2,-1,　3,-1
-1,　1,　1,-1, 4,-1,-1,-1,　3,-1
-1,-1,-1,-1,　4, 4,　4,-1,　3,-1
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1

と言う状態になっている筈です。