P1387 最大正方形-前缀和

最大正方形

题目描述

在一个 $n\times m$ 的只包含 $0$ 和 $1$ 的矩阵里找出一个不包含 $0$ 的最大正方形，输出边长。

输入格式

输入文件第一行为两个整数 $n,m(1\le n,m\le 100)$，接下来 $n$ 行，每行 $m$ 个数字，用空格隔开，$0$ 或 $1$。

输出格式

一个整数，最大正方形的边长。

样例 #1

样例输入 #1

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1
1
2
3
4
5

样例输出 #1

2
1

#include 
using namespace std;
#define sf(x) scanf("%d",&x);
#define de(x) cout<<x<<" ";
#define Pu puts("");
typedef long long ll;
const int N=1e2+10;
int a[N][N];
int pre[N][N];
int n,m,ans;
int fun(int t){
    int l,r,u;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            l=i+t-1;r=j+t-1;
            if(l>n||r>m||i-1<0||j-1<0) continue;
            u=pre[l][r]-pre[i-1][r]-pre[l][j-1]+pre[i-1][j-1];
            if(u==t*t) return 1;
        }
    }
    return 0;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sf(a[i][j])
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
        }
    }
    for(int i=100;i>=1;i--){
        if(fun(i)){
            ans=i;
            break;
        }
    }
    de(ans)
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43