题目描述

在一个由 0 和 1 组成的 n×m 的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

样例

输入格式
第一行包含两个整数 n,m，表示二维矩阵大小。

接下来 n 行，每行包含 m 个整数，每个整数只可能是 0 或 1。

输出格式
输出只包含 1 的最大正方形的面积。

数据范围
1≤n,m≤1000
输入样例：
4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出样例：
4

算法1

(dp) $O(nm)$

f[i][j]代表以i行j列结尾的点的边长，所以只有输入的点是1的时候才可以更新，我们在更新的当前点的时候实际上是取决于它上方的边长，左边的边长和左上角的边长，由水桶定律我们知道最大的边长取决于最小的边，所以我们最小的边来更新就可以了。

C++ 代码

#include<bits/stdc++.h>
using namespace std; 
const int N=1010;
int a[N][N],f[N][N];
int main()
{
    int n,m;
    cin>>n>>m;
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int x;
            cin>>x;
            if(x==1) f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
            ans=max(ans,f[i][j]);
        }
    cout<<ans*ans;
    return 0;
}