如何在一个方阵中找到最大全一子方阵？

Question

一个边长为N(N

Answer 1

#include
#include
#defineMAX1000
intmatrix[MAX][MAX]={{0}};
intmain()
{
//freopen("input.txt","r",stdin);
inti,j;
intmax=1;
intsize;
scanf("%d",&size);
for(i=0;ifor(j=0;jscanf("%d",&matrix[i][j]);
for(i=1;ifor(j=1;jif(matrix[i][j]==1)
{
intmin=0;
min=matrix[i-1][j]>matrix[i][j-1]?matrix[i][j-1]:matrix[i-1][j];
min=min>matrix[i-1][j-1]?matrix[i-1][j-1]:min;
matrix[i][j]=min+1;
max=max}
printf("%d",max);
return0;
}
                            

Answer 2

这个方法复杂度不是最优的，不过好想。
首先预处理后我们可以O(1)求出每个子矩（不一定方）阵的1个数。
然后枚举方阵左上角，二分子方阵边长判断这个子方阵是不是全1的。
复杂度O(n^2logn)，1000可过。
啊还是写写代码：
intx[1001][1001];
inty[1001][1001]={0};
inti,j,k,n,l,r,res;
//输入n,x
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
y[i][j]=y[i][j-1]+x[i][j];
for(j=1;j<=n;j++)
y[i][j]+=y[i-1][j];
}
#defineall_1(a,b,n)(y[(a)+(n)-1][(b)+(n)-1]-y[(a)-1][(b)+(n)-1]-y[(a)+(n)-1][(b)-1]+y[(a)-1][(b)-1]==(a)*(b))
res=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
l=0;
r=n-i-1;
while(lmid=(l+r)/2;
if(all_1(i,j,mid))
l=mid;
else
r=mid;
}
if(all_1(i,j,r))
res=max(res,r);
else
res=max(res,l);
}
//输出res