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

Question

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

Answer 1

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int matrix[MAX][MAX] = {{0}};

int main()
{
    //freopen("input.txt", "r", stdin);

    int i, j;
    int max = 1;
    int size;

    scanf("%d", &size);
    for(i=0; i<size; i++)
        for(j=0; j<size; j++)
            scanf("%d", &matrix[i][j]);

    for(i=1; i<size; i++)
        for(j=1; j<size; j++)
            if(matrix[i][j] == 1)
            {
                int min = 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<matrix[i][j] ? matrix[i][j] : max;
            }

    printf("%d", max);

    return 0;
}

Answer 2

这个方法复杂度不是最优的，不过好想。
首先预处理后我们可以 O(1) 求出每个子矩（不一定方）阵的 1 个数。
然后枚举方阵左上角，二分子方阵边长判断这个子方阵是不是全 1 的。
复杂度 O(n^2 log n)， 1000 可过。

啊还是写写代码：

int x[1001][1001];
int y[1001][1001] = {0};
int i, 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];
}
#define all_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 (l < r) {
            mid = (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

Answer 3

开两个数组heng[i][j],shu[i][j]，表示（i,j）这个格子横着向左有heng[i][j]个连续的1(包括它本身)，向上有shu[i][j]个连续的1.heng[i][j]和shu[i][j]可以在读入矩阵的时候就预处理
if(当前格子!=1){heng[i][j]=1}else{heng[i][j]=heng[i][j-1]+1}
else{heng[i][j]=0}
shu[i][j]也是同样的处理
在计算heng[i][j]&shu[i][j]的同时就能计算以(i,j)为右下角的合法矩形的最大面积了。
比如heng[i][j]=8 shu[i][j]=5，那么以(i,j)为右下角的矩形最大的可能面积不超过40，最大面积计算应该是 for(x=i; heng[x][j]>0; x--){w = min(w,heng[x][j])} ans=w*shu[i][j]