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

質問

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 · ベストアンサー

#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;
}

お礼

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

回答No.3

Tiffa9900

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

【メイン処理（開始）】

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

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

お礼

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

回答No.2

Tiffa9900

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

任意の２点を(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

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

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

お礼

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