最大正方形1612
图图搬运侵删

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int a[N][N],f[N][N];//以(i, j)为右下角的最大正方形的边长
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int res = 0,area;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==1)//代表以i行j列结尾的点的边长，所以只有输入的点是1的时候才可以更新
            f[i][j]= min(f[i-1][j],min(f[i][j-1], f[i-1][j-1]))+1;//我们在更新的当前点的时候实际上是取决于它上方的边长，左边的边长和左上角的边长
            //由水桶定律我们知道最大的边长取决于最小的边，所以我们最小的边来更新就可以了
                res=max(res,f[i][j]);//只包含 1 的最大正方形
                area=res*res;
        }
    }
    cout <<area<<endl;
    return 0;
}