質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.59%

白黒画像の数を求めるプログラムがどうやっていいのかわかりません。

受付中

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 713

chihiro_0701

score 10

今回の問題点

C言語初心者です。
下記のプログラムをサンプルプログラムを見ながら作成しては見たものの、うまくいかずに苦戦しています。
わかりづらい部分や、丸投げになってしまうかもしれませんが、どうぞよろしくお願いします。

問題

下記を参考にして,次の画像データで同様にある地点からぬりつぶし処理を行った結果,連結された画素数を答えるプログラムを作成せよ.塗りつぶし開始位置は,キーボードから入力させた数字がxのとき,座標(x,x)からとする.画像データは上記と異なり,12×12とする.当然,課題のプログラム中のデータはこれに合わすように変更する点に注意.

補足

画像処理や迷路を探索するロボットのプログラムでは,塗りつぶしルーチンによく用いられる.例えば9×9の白黒二値画像があったとする.このまんなかの(5,5)から塗りつぶしを行う.塗りつぶしとはその座標に連結している黒画素を抜き出す操作である.

□■■□□□□□□
■■□■■■■■□
□□□□■□■□□
■■□□■■■□□
■□□□■■□□□
□□□□□■□□□
□■■■■■■□■
□■□□□□□■□
■□□□□□□■□
この結果次の画像が出力されるはずである.

□□□□□□□□□
□□□■■■■■□
□□□□■□■□□
□□□□■■■□□
□□□□■■□□□
□□□□□■□□□
□■■■■■■□□
□■□□□□□□□
□□□□□□□□□
ここで,連結しているかどうかは上下左右の4方向だけで判定する.(これを4連結と呼ぶ.ちなみに斜めも含めて判定する場合には,8連結と呼ぶ.)

出題画像

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

参考

このような塗りつぶしを実現するには,再帰を用いる.

これを再帰呼出を利用して実現するには,次のような関数を用意するものとする.

int fill(int x, int y);        //塗りつぶし関数
入力画像のデータは上記の画像の白を0,黒を1としてあらかじめ初期化しておく.出力画像のデータはすべて白(0)とする.

関数fillは,座標(x,y)から塗りつぶしを始めて,塗りつぶした画素の数を返すとする.ただし, 座標は左上を(0,0)とし右下を(8,8)とする.また,返値だけでなく塗りつぶした画素位置に相当するoutputの(x,y)をすべて1,ぬりつぶした領域外は0のままとする.

実際にプログラムを作成してみたができない。

include <stdio.h>

int fill(int x, int y);
int input[12][12] = {
{0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,1,1,0,0,0,0,0,0,0,1},
{0,1,0,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,1,0,1,0,0,0,1},
{0,1,1,1,0,1,1,1,0,1,1,1},
{0,1,0,0,0,1,1,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,1,0,1},
{0,0,1,1,1,1,1,1,0,1,0,1},
{0,1,1,0,0,0,1,0,1,0,0,1},
{0,1,0,0,0,0,1,0,1,0,0,1},
{0,0,1,1,1,1,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,0,1,1,1},
};

int output[12][12] = {
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0,0,0},
};

int main(void)
{
int a,x,n,left,right,up,down;
scanf("%d", &x); //xをキーボードから入力
if(x>=12){
n=0;
printf("%d",n);
return 0;
}
n = fill(x, x); //座標x,xから塗りつぶすことにする
while((left==0)&&(right==0)&&(up==0)&&(down==0)){
n = fill(x-1,x);
left=left+n;
n = fill(x+1,x);
right=right+n;
n = fill(x,x-1);
up=up+n;
n = fill(x,x+1);
down=down+n;
}
a=left+right+up+down;
printf("%d\n",a);
return 0;
}

int fill(int x, int y)
{
int a,n;
if(input[x][x]==0){
n=0;
return n;
}
if(output[x][x]==1){
n=1;
return n;
}else{
output[x][x]=1;
n=0;
return n;
}
}

サンプルプログラム

#include <stdio.h>
int fill(int x, int y);
int input[9][9] = {
{0,1,1,0,0,0,0,0,0},
{1,1,0,1,1,1,1,1,0},
{0,0,0,0,1,0,1,0,0},
{1,1,0,0,1,1,1,0,0},
{1,0,0,0,1,1,0,0,0},
{0,0,0,0,0,1,0,0,0},
{0,1,1,1,1,1,1,0,1},
{0,1,0,0,0,0,0,1,0},
{1,0,0,0,0,0,0,1,0}
};
int output[9][9] = {
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
};

int main(void)
{
int x,n;
scanf("%d", &x); //xをキーボードから入力
n = fill(x, x); //座標x,xから塗りつぶすことにする
printf("%d\n",n);
return 0;
}

int fill(int x, int y)
{
int left,right,up,down;
座標(x,y)がinputの範囲外であればダメ(0を返す)
inputの座標(x,y)を調べる.黒(1)でなければダメ(0を返す)
outputの座標(x,y)を調べる.すでに出力があれば(1ならば)ダメ(0を返す)
そうでないなら
outputの(x,y)を黒(1)に置き換える.
自分の上下左右を調べる.
つまり,left = fill(x-1, y);
right = fill(x+1,y);
up = fill(x,y-1);
down = fill(x,y+1);
返値は,left+right+up+down+1; //+1は自分自身の1画素分
}
たったこれだけで,複雑な塗りつぶしルーチンを記述できてしまう.

再帰プログラミングのポイントは,作成中の関数が予定どおりに動作できると思い込んでプログラムすることである.この場合,fillがちゃんと動作して,ちゃんと塗りつぶしを行って面積も正しく返してくれることを期待して,このように書き下す.

実行例

5         ←キーボードから入力
20      ←20画素が連結されていた

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • fana

    2018/11/26 10:33

    サンプル(というかもう答えそのものに見えるが)があるようですし,まずはそれに沿った形でやってみた方がよろしいのでは…?

    キャンセル

回答 1

0

簡単には、二重ループで、変化が無くなった時点で終了とする。で、できると思いますが、、。

input(x, y) = 2;
bool found;

do {
  int xx, yy;
  found = false;
  for (yy = 0; yy < 9; yy++) {
    for (xx = 0; xx < 9; xx++) {
    input(xx, yy)が 1 で、
       座標 (xx, yy) の4連結に '2' となる input(?, ?)があれば、
          input(xx, yy) = 2;  //とする。
          flag = true;
    }
  }
} while (found);
抜けた時の input2の場所が連結要素。

こんなのではダメ? (再帰じゃないけど)  効率は悪そう、、。
コード書いてみたいけど、時間が無くなったので。


沢山、質問を上げているようですが、全て同時? それとも宿題の山?

[追記]
再帰で書いてみました。もうちょっと面白いかと思ったのですが、簡単だったので、そのまま。
(元の入力データを書き換えています)

void fill(int x, int y)
{
    if ((x < 0) || (y < 0) || (x >= 12) || (y >= 12))    return;
    if (input[x][y] != 1)    return;
    input[x][y] = 2;
    fill(x - 1, y);
    fill(x, y - 1);
    fill(x + 1, y);
    fill(x, y + 1);
}

ところで、質問の主旨は何だったのでしょうか?

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.59%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る