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

Question

一个边长为N(N<=1000)的方阵，其元素为随机的1或0，如何快速找出其中【边长最大的】【元素全为1的】子方阵边长？

Answer 1

#include#include#defineMAX1000intmatrix[MAX][MAX]={{0}};intmain(){//freopen("input.txt","r",stdin);inti,j;intmax=1;intsize;scanf("%d",&size);for(i=0;i

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,xfor(i=1;i