二次元配列を調べ、隔離されたマス（穴）の個数を調べる

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら
閉鎖
学生A

二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#1

投稿記事 by 学生A » 14年前

お初です。

コード: 

#include <stdio.h>

void init(); //初期化
int countHole(); //穴の個数カウント

//画面の配列
int array[10][10];

//メイン
int main(void)
{
	int i,j,value;
	
	init();
	value=countHole();　/* 穴の数をカウントして変数valueに代入 */
	
	//画面表示
	for(i=0;i<=9;i++) {
		for(j=0;j<=9;j++) {
			if (array[j][i]==1) {
				printf("■");
			} else {
				printf("□");	
			}
		}
		printf("\n");
	}
	printf("\n穴の個数：%d個\n",value);
	
	scanf("終わり");
	return 0;
}

//初期化
void init() {
	
	int i,j;
	
	//全て0にする
	for (i=0;i<=9;i++) {
		for(j=0;j<=9;j++) {
			array[i][j]=0;	
		}
	}
	
	//特定のマスだけ1にする
	array[0][8]=1;
	array[1][8]=1;
	array[2][8]=1;
	array[2][9]=1;
	
}

int countHole() {
	
	/* ここで穴の個数をカウント */
	return 0;
}
上記のようなプログラムを実行すると、
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
■■■□□□□□□□
□□■□□□□□□□

穴の個数：0個

と表示されます。
ここで、左下の隔離されたマス（穴）の数を調べて、変数valueに代入したいのですが、出来ますか？
この場合だと「2個」と表示されるのが期待です。
ただし、調べるときは一番上から調べます。
例えば、

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

だと下の領域を穴と認識し、「80個」と表示されて欲しいです。（左、下、右端には壁があって、上には無いって感じ？かな）

分かりにくくてすいません。ご教授願います。
ページトップ
学生A

Re: 二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#2

投稿記事 by 学生A » 14年前

すいません。サンプルの15行目に全角スペースが紛れ込んでいたようです。正しくは以下です。

コード: 

#include <stdio.h>
 
void init(); //初期化
int countHole(); //穴の個数カウント
 
//画面の配列
int array[10][10];
 
//メイン
int main(void)
{
    int i,j,value;
    
    init();
    value=countHole(); /* 穴の数をカウントして変数valueに代入 */
    
    //画面表示
    for(i=0;i<=9;i++) {
        for(j=0;j<=9;j++) {
            if (array[j][i]==1) {
                printf("■");
            } else {
                printf("□");  
            }
        }
        printf("\n");
    }
    printf("\n穴の個数：%d個\n",value);
    
    scanf("終わり");
    return 0;
}
 
//初期化
void init() {
    
    int i,j;
    
    //全て0にする
    for (i=0;i<=9;i++) {
        for(j=0;j<=9;j++) {
            array[i][j]=0;  
        }
    }
    
    //特定のマスだけ1にする
    array[0][8]=1;
    array[1][8]=1;
    array[2][8]=1;
    array[2][9]=1;
    
}
 
int countHole() {
    
    /* ここで穴の個数をカウント */
    return 0;
}
ページトップ
アバター
h2so5
副管理人
記事: 2212
登録日時: 14年前
住所: 東京
連絡を取る:
h2so5 に連絡する

Re: 二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#3

投稿記事 by h2so5 » 14年前

学生A さんが書きました: ここで、左下の隔離されたマス（穴）の数を調べて、変数valueに代入したいのですが、出来ますか？
この場合だと「2個」と表示されるのが期待です。
ただし、調べるときは一番上から調べます。
私の思いつく方法では、

１.まずマス[0,0]を調べます。
2.そのマスに0が入っていた場合： そのマスに2を代入し、 そのマスの周囲の８マスを同様に調べます
　　そのマスに0以外が入っていた場合： 何もしません

周囲の８マスに対して、上の1,2を繰り返します。
周囲の８マスに０が無くなるまで繰り返されます。

★□□□□□□□□□　　　　★・・・調べるマス
□□□□□□□□□□　　　　　□・・・０が入っている
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
１１１□□□□□□
□□１□□□□□□□


２★□□□□□□□□　　　　★・・・調べるマス
★★□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
１１１□□□□□□
□□１□□□□□□□

２２★□□□□□□□　　　　★・・・調べるマス
２２★□□□□□□□
★★★□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
１１１□□□□□□
□□１□□□□□□□

・
・
・

２２２２２２２２２２　　　　★・・・調べるマス
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２★□□□□□□
１１１★□□□□□　　　　　　←１の場合、その周囲のマスは調べない
□□１□□□□□□□

・
・
・

２２２２２２２２２２　　　　
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
２２２２２２２２２２
１１１２２２２２２２　　　
□□１２２２２２２２

このようにすると、隔離されていないマスは全て1か2で埋まるため、
0の個数を調べれば穴の数を出すことができます。
ページトップ
フリオ

Re: 二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#4

投稿記事 by フリオ » 14年前

穴の定義がよくわからないのですが、
□□□□□□□□□□
■■■■■■■■■■
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
■■■■■■■■■■
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
や、
□■□■□□□□□□
□■□■□□□□□□
□■■■□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
□□□□□□□□□□
等はどうなるのでしょうか。
ページトップ
学生A

Re: 二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#5

投稿記事 by 学生A » 14年前

返信ありがとうございます。

＞フリオさん
定義があいまいでしたね。
調べる際は、h2so5さんの通り(0,0)から調べることにします。
また、(0,0)=1となることは無いことにします。
穴の中で更に隔離された場合は、どちらも穴とすることにします。
よって

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

は70個


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

は２個となります。

＞h2so5さん
ありがとうございます。
ぎりぎり組めそうなので頑張ってみます！
組めたらまた投稿します。
ページトップ
学生A

Re: 二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#6

投稿記事 by 学生A » 14年前

出来ました。h2so5さん、フリオさん、ありがとうございます！
コードは以下のようになりました。

コード: 

#include <stdio.h>
 
void init(); //初期化
void fillArray(int targetX,int targetY); //arrayを2で埋める
int isOK(int targetX,int targetY); //調べて良い座標か調べる
 
//画面の配列
int array[10][10];
 
//メイン
int main(void)
{
    int i,j,value=0;
    
    init();
    fillArray(0,0); /* (0,0)から隔離されていないマスを2で埋める */
    
    //画面表示＆マスカウント
    for(i=0;i<=9;i++) {
        for(j=0;j<=9;j++) {
        	switch (array[j][i]) {
            case 0:
                printf("□");
                value++;
                break;
            case 1:
                printf("■");
                break;
            case 2:
            	printf("□");
            	break;
        	}
        }
        printf("\n");
    }
    printf("\n穴の個数：%d個\n",value);
    
    scanf("終わり");
    return 0;
}
 
//初期化
void init() {
    
    int i,j;
    
    //全て0にする
    for (i=0;i<=9;i++) {
        for(j=0;j<=9;j++) {
            array[i][j]=0;  
        }
    }
    
    //特定のマスだけ1にする
    array[0][8]=1;
    array[1][8]=1;
    array[2][8]=1;
    array[2][9]=1;
    
}

//arrayを2で埋める
void fillArray(int targetX,int targetY) {
    
    //指定された座標が空白かどうか調べる
    if (array[targetX][targetY] == 0) {
    	
    	//その座標に2を代入
        array[targetX][targetY] = 2;
        
        if ( isOK( targetX + 1 , targetY ) == 1 ) {
            fillArray( targetX + 1 , targetY );
        }
        if ( isOK( targetX - 1 , targetY ) == 1 ) {
            fillArray( targetX - 1 , targetY );
        }
        if ( isOK( targetX , targetY + 1 ) == 1 ) {
            fillArray( targetX , targetY + 1 );
        }
        if ( isOK( targetX , targetY - 1 ) == 1 ) {
            fillArray( targetX , targetY - 1 );
        }

    }
}

//調べて良い座標か調べる
int isOK(int targetX, int targetY) {

    if (targetX > -1 && targetX < 10 && targetY > -1 && targetY < 10) {
        if (array[targetX][targetY] == 0) {
            return 1;
        } else {
            return 0;
        }
    } else {
        return 0;
    }
    
    return 0;

}
なんか冗長な感じになりましたが（再起処理を初めて書いたので＾＾；　もう少し短く書けるところがあれば教えてください。）、要件は満たしたので解決とします。
ページトップ
non
記事: 1097
登録日時: 14年前

Re: 二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#7

投稿記事 by non » 14年前

いいと思います。短くしたいなら、判断の場所(タイミング）と、returnをうまく使うことでしょうか。
たとえば、こうなります。

コード: 

void fillArray(int targetX,int targetY) {

	if (targetX < 0 || targetX >9 | targetY <0  || targetY >9) 
		return;
	//指定された座標が空白かどうか調べる
	if (array[targetX][targetY] != 0) 
		return;

	//その座標に2を代入
	array[targetX][targetY] = 2;

	fillArray( targetX + 1 , targetY );
	fillArray( targetX - 1 , targetY );
	fillArray( targetX , targetY + 1 );
	fillArray( targetX , targetY - 1 );
}
non
ページトップ
学生A

Re: 二次元配列を調べ、隔離されたマス（穴）の個数を調べる

#8

投稿記事 by 学生A » 14年前

＞nonさん
なるほど、別にisOKなどの関数を作らなくても、条件に合致しない場合はreturnして強制終了すれば良い　ということですね。
これはもしかすると、再帰処理全般に言えることなのかもしれない・・・　とも思いました。

参考になりました。ありがとうございます。
ページトップ
閉鎖

“C言語何でも質問掲示板” へ戻る