最大の四角形を求めるプログラム

C言語の問題です

5×5マスに0か1の数値が入っています。
1が入っているマスで最大の大きさになる四角形を求める問題です

例
入力
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
結果:5

入力
1 1 1 1 0
1 1 1 0 0
1 1 0 0 0
1 0 0 0 0
0 0 0 0 0
結果:6

入力
0 1 1 1 0
0 0 1 0 1
1 0 1 1 1
0 0 1 1 1
0 0 1 0 0
結果:6

このような具合です。
どうやって作ればよいのかまったく分かりません。
よろしくお願いします。

No.4 ベストアンサー 回答者： himajin100000 回答日時： 2008/06/19 23:16

#include <stdio.h>

#define W (5)
#define H (5)

//何か大いに間違えてそうなので突っ込み歓迎。
//デバッグに時間がかかってしまった。

int table[W][H] = {
{0, 1, 1, 1, 0},
{0, 0, 1, 0, 1},
{1, 1, 1, 1, 1},
{0, 1, 1, 1, 1},
{0, 0, 1, 0, 0}
};


int check(int x,int y){
int current = 0;
int jmax = H;
int pass = 0;
int i;
int j;
if (table[ x ][ y ] == 0){
return 0;
}
for (i = 0 ; ((x + i < W) && (table[ x + i ][ y ] == 1)) ; i++){

for (j = 0; y + j < H;j++){
if ((table[x + i][y + j] == 0)){
pass = 1;
if (j > jmax){
j = jmax;
}else{
jmax = j;
}

if ((i + 1) * j > current){
current = (i + 1) * j;
}
break;
}

}
if (pass == 0){

current = (i + 1) * (H - y);

}
}

return current;

}

int main(){
int max = 0;
int i;
int j;
for (i = 0;i < W; i++){
for (j = 0; j < H;j++){
int temp = check(i,j);
if (temp > max){
max = temp;
}
}
}

printf("%d",max);
return 0;
}

この回答へのお礼

わざわざ作っていただけたんですね。ありがとうございます！
感激ですよ～。ただ、つい先ほど私も見てくれは悪いですが動作するものが完成しました。
タイミングが悪くて本当に申し訳ないです。このプログラムもきちんと読んで参考にさせていただきます。

お礼日時：2008/06/20 01:10

No.3 回答者： Tiffa9900 回答日時： 2008/06/19 21:42

すみません。

ちょっと訂正です。
改めて見直したら、誤字があったり、バグがあったり、色々と効率の悪い事をしていました。


【メイン処理（開始）】

S_MAX=0

FOR X1=1～5
　FOR Y1=1～5
　　FOR X2=X1～5 ### 修正
　　　FOR Y2=Y1～5 ### 修正

　　　　【面積を求める処理】

　　　　IF S_MAX < S THEN
　　　　　S_MAX = S
　　　　END IF

　　　NEXT
　　NEXT
　NEXT
NEXT

RETURN S_MAX ### 修正

【メイン処理（終了）】



【面積を求める処理（開始）】

S=0

FOR X=X1～X2
　FOR Y=Y1～Y2

　　IF (X,Y) = 1 THEN
　　　S=S+1
　　ELSE
　　　S=0
　　　【面積を求める処理】を抜ける
　　END IF

　NEXT
NEXT

【面積を求める処理（終了）】

この回答へのお礼

ありがとうございます～。
やはり、こういうアルゴリズムになりますか。
どうにか動くものが出来ました。ありがとうございます。

お礼日時：2008/06/20 01:09

No.2 回答者： Tiffa9900 回答日時： 2008/06/19 20:57

Ｃを知らないから考え方だけですが、私ならこうやるかな？

任意の２点を(X1,Y1),(X2,Y2)として、
それが作る四角形で最大を見つける。

【メイン処理（開始）】

S_MAX=0

FOR X1=1～5
　FOR Y1=1～5
　　FOR X2=1～5
　　　FOR X2=1～5

　　　　【面積を求める処理】

　　　　IF S_MAX < S THEN
　　　　　S_MAX = S
　　　　END IF


　　　NEXT
　　NEXT
　NEXT
NEXT

RETURN S

【メイン処理（終了）】



【面積を求める処理（開始）】

S=0

FOR X=X1～X2
　FOR Y=Y1～Y2

　　IF (X,Y) = 1 THEN
　　　S=S+1
　　ELSE
　　　S=0
　　　【面積を求める処理】を抜ける
　　END IF

　NEXT
NEXT

【面積を求める処理（終了）】

No.1 回答者： hid_hid_hid 回答日時： 2008/06/19 20:20

X座標、Y座標で2重ループを作り、１をサーチ。

見つけたら、連続でX方向に何個あるか個数を格納。[xn]とする。
最初に見つけた１の座標から、Y方向に連続していくつあるかをサーチ（ここにも2重ループで、四角い範囲を検索し、最大連続列を記録[yn]とする）
MaxNow=[xn]*[yn];
if(MaxNow>Max)　Max=MaxNow;
ここが最初の二重ループの閉端

まず、頭でどう考えるかですね。

この回答へのお礼

無事解決できました。
ありがとうございます。

お礼日時：2008/06/20 01:07