/*
0と1で構成されている長方形の中に含まれる、1で構成される長方形の最大の大きさを求める
例
11010 01011 11110
01111 01010 01110
10101 → 4 00100 → 3 01101 → 8
01110 00110 01110
01100 10100 00001
*/
#include<stdio.h>
#include<stdlib.h>
int func(int **arr,int x,int y,int m,int n)
{
int i,j;
int flg;
int size[2]={0};
flg=1;
for(i=x;i<x+m;i++){
if(arr[i][y+n]==0){ //縦方向に1増やし長方形が作れるか検討
flg=0;
break;
}
}
if(flg==1)size[0]=func(arr,x,y,m,n+1); //縦方向（下）に1増やし計算
flg=1;
for(j=y;j<y+n;j++){
if(arr[x+m][j]==0){ //横方向に1増やし長方形が作れるか検討
flg=0;
break;
}
}
if(flg==1)size[1]=func(arr,x,y,m+1,n); //横方向（右）に1増やし計算
if(size[0]==0&&size[1]==0)return m*n; //長方形が作れなかったとき、そのときの長方形のサイズを返す
if(size[0]>size[1])return size[0]; //縦方向に1増やした方が大きい場合
else return size[1]; //横方向に1増やした方が大きい場合
}
void InputNum(int ***arr,int num,int m,int n)
{
int i,j,t,flg;
char str[100];
for(t=0;t<num;t++)
for(j=0;j<n;j++)
for(i=0;i<m;i++)
arr[t][i][j]=-1; //初期値として-1を入れておく
printf("0または1を入力し、%d×%d（横×縦）の長方形を作成してください\n",m,n);
t=0;
do{
printf("%d回目の入力\n",t+1);
for(j=0;j<n;j++){
fgets(str,m+1,stdin);
fflush(stdin);
for(i=0;i<m;i++)arr[t][i][j]=str[i]-'0';
}
flg=1;
for(j=0;j<n;j++)
for(i=0;i<m;i++)
if(arr[t][i][j]!=0&&arr[t][i][j]!=1)
flg=0; //0,1以外の値が入った場合flgに0を入れる
if(flg==1)t++; //flgが1なら（0または1の値が入力されてたら）tを増分
else printf("入力ミス\n");
}while(t<num);
}
int main(void)
{
int i,j,t,buf,size;
int num,m,n;
int ***arr;
printf("回数を入力してください（1以上） : ");
num=fgetc(stdin)-'0';
fflush(stdin);
printf("横幅を入力してください（1以上） : ");
m=fgetc(stdin)-'0';
fflush(stdin);
printf("縦幅を入力してください（1以上） : ");
n=fgetc(stdin)-'0';
fflush(stdin);
arr=(int ***)malloc(sizeof(int **)*num); //メモリの確保（num×(m+1)×(n+1)×sizeof(int)）
for(t=0;t<num;t++){ //横、縦方向に余分に1つ確保しておく→m+1,n+1
arr[t]=(int **)malloc(sizeof(int *)*(m+1));
for(i=0;i<m+1;i++)arr[t][i]=(int *)malloc(sizeof(int)*(n+1));
}
InputNum(arr,num,m,n); //arr(0:num-1,0:m-1,0:n-1)に0または1を入れる
for(t=0;t<num;t++){
for(i=0;i<m;i++)arr[t][i][n]=0; //InputNumで入力されてない部分（余分に確保しておいた部分）に0を入れる
for(j=0;j<n;j++)arr[t][m][j]=0;
arr[t][m][n]=0;
}
for(t=0;t<num;t++){
size=0;
for(j=0;j<n;j++){
for(i=0;i<m;i++){
if(arr[t][i][j]==1){ //(0,0)から走査して1を探索
buf=func(arr[t],i,j,1,1);
if(size<buf)size=buf;
}
}
}
printf("%d回目:結果=%d\n",t+1,size);
}
for(t=0;t<num;t++){
for(i=0;i<m+1;i++)free(arr[t][i]);
free(arr[t]);
}
free(arr);
return 0;
}
/*
例
a｜ 0 1 2 3 4
─┼───────-
0│ 0 1 1 1 0
1｜ 1 1 0 0 0
2｜ 0 1 1 1 0
3｜ 1 0 1 1 0
4｜ 0 0 0 0 0
i=1,j=0
m=1,n=1
a｜ 0 1 2 3 4 [] : a[i][j]
─┼───────- () : a[i+m][j]=1 → 長方形が作れる → m=2,n=1（m++）
0│ 0 [1](1) 1 0 a[i][j+n]=1 → 長方形が作れる → m=1,n=2（n++）
1｜ 1 (1) 0 0 0
2｜ 0 1 1 1 0
3｜ 1 0 1 1 0
4｜ 0 0 0 0 0
m=2,n=1
a｜ 0 1 2 3 4 [] : a[i][j],a[i+1][j]
─┼───────- () : a[i+m][j]=1 → 長方形が作れる → m=3,n=1
0│ 0 [1][1](1) 0 a[i ][j+n]=1
1｜ 1 (1)(0) 0 0 a[i+1][j+n]=0 → 長方形が作れない（0があるため）
2｜ 0 1 1 1 0
3｜ 1 0 1 1 0
4｜ 0 0 0 0 0
m=3,n=1
a｜ 0 1 2 3 4 [] : a[i][j],a[i+1][j],a[i+2][j]
─┼───────- () : a[i+m][j]=0 → 長方形が作れない
0│ 0 [1][1][1](0) a[i ][j+n]=1
1｜ 1 (1)(0)(0) 0 a[i+1][j+n]=0
2｜ 0 1 1 1 0 a[i+2][j+n]=0 → 長方形が作れない
3｜ 1 0 1 1 0
4｜ 0 0 0 0 0
m=1,n=2
a｜ 0 1 2 3 4 [] : a[i][j],a[i][j+1]
─┼───────- () : a[i+m][j ]=1
0│ 0 [1](1) 1 0 a[i+m][j+1]=0 → 長方形が作れない
1｜ 1 [1](0) 0 0 a[i][j+n]=0 → 長方形が作れない
2｜ 0 (0) 1 1 0
3｜ 1 0 1 1 0
4｜ 0 0 0 0 0
*/