Cuvism²

题目描述

s7h 喜欢正方形，而且越大越好！

现在， s7h 拿到了一个由 0 和 1 组成的二维图形，他想知道这个二维图形中由 1 组成的最大的正方形的边长。

输入

第一行输入一个整数 T，代表数据组数

对于每组数据，第一行输入两个正整数 $n,m$，分别代表二维图形的长，高。

接下来 $m$ 行，每行 $n$ 个数字，每个数字之间用空格隔开。第 $i$ 行第 $j$ 列为 1 代表 $(i,j)$ 这个坐标有一个长宽为 1 的正方形，如果为 0 代表此处为空（数据保证保证这些数字只能是 0 或 1）。

数据保证 $n,m\le 2000$。

输出

对于每组数据一个正整数，代表二维图形中由 1 组成的正方形的最大边长。不同组数据间用换行隔开。

输入样例

1
3 3
1 0 0
0 1 1
0 1 1

输出样例

2

bug code

#include<stdio.h>
int l,r,n,m,mid,a[2005][2005],sum[2005][2005],T;
//sum[i][j]:record the sum of every integer from a[0][0] to a[i][j] 
int check(int x){
    //this function is used to check if there exists a square of length x
    //if exists, return 1    
    for(int i=0;i<=n-x;++i){
        for(int j=0;j<=m-x;++i){
            if(sum[i+x][j+x]-sum[i][j]==x*x){
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                scanf("%d",a[i][j]);
                sum[i][j]=sum[i-1][j-1]+a[i][j];
            }    
        }
        r=n>m?m:n;
        l=1;
        mid=(l+r)/2;
        while(l<r){//use binary search to find the biggest length of the square
            if(check(mid))    l=mid;
            else    r=mid-1;
            mid=(l+r)/2;
        }
        printf("%d\n",mid);
    }
    return 0;
}

注：

前缀和算法：

预处理 $sum[i]=sum[i-1]+a[i]$，计算 $sum[r]-sum[l-1]$ 即可得到 $\sum_{i=l}^r a[i]$ 的值。

作用到二维，如果一个区间和等于面积，则可以判断这个区间被 1 填满