【luogu1387】最大正方形

题目描述

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

输入

输入文件第一行为两个整数n,m（1<=n,m<=100），接下来n行，每行m个数字，用空格隔开，0或1.

输出

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

样例输入

4 4
0 1 1 1
1 1 1 0
0 1 1 0
1 1 0 1

样例输出

2

---

题解

巨大的水题。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=100+5;

int n,m,map[maxn][maxn],dp[maxn][maxn],maxx;

int minn(int x,int y,int z){
    return min(x,min(y,z));
}

template<typename T>void read(T& aa){
    char cc; ll ff;aa=0;cc=getchar();ff=1;
    while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();
    if(cc=='-') ff=-1,cc=getchar();
    while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
    aa*=ff;
}

int main(){
    read(n),read(m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        read(map[i][j]);
        if(map[i][j]==1) dp[i][j]=minn(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
        maxx=max(maxx,dp[i][j]);
    }
    cout<<maxx<<endl;
    return 0;
}