题目描述

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

动态规划

时间复杂度 Ｏ(n^3), 思路清晰，但出现大量重复计算，直接导致超时

C++ 代码

#include <iostream>
#include <cmath>

using namespace std;

const int N=1010;
int n,m;
int a[N][N],dp[N][N];       //dp[i][j]表明以i,j为右下角的最大正方形边长
int ans;                    //最终最大边长

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(a[i][j]==0){
                dp[i][j]=0;         //如果该位置为0，则不可能构成正方形，且不会超过最大边长
                continue;
            }
            if(i>0&&j>0){
                if(dp[i-1][j-1]==0){        //如果左上角的最大边长为0，则该位置构成最大边长只能为1
                    dp[i][j]=1;
                }else{
                    int k=dp[i-1][j-1]+1;       //可能构成最大正方形变长的最大值
                    int leftMax=k,upMax=k,allMin;       //左连续1的最大长度，上连续1的最大长度，总最小边长
                    for(int p=2;p<=k;p++){
                        if(a[i][j-p+1]==0){
                            leftMax=p-1;            //确定左连续1长度
                            break;
                        }
                    }
                    upMax=leftMax;                  //由于是正方形，有意义的上连续1的最大值不会超过lefeMax
                    for(int p=2;p<=leftMax;p++){
                        if(a[i-p+1][j]==0){         //确定上连续1最大长度
                            upMax=p-1;
                            break;
                        }
                    }
                    allMin=upMax;                   //以该位置为右下角可能构成正方形的最大边长
                    dp[i][j]=allMin;
                }
            }
            ans=max(ans,dp[i][j]);                  //确定最大边长
        }
    }
    cout<<ans*ans<<endl;            //输出面积
    return 0;
}

算法2

优化后的动态规划

时间复杂度 Ｏ(n^2) 每次利用前面计算的结果，避免重复计算

C++ 代码

#include <iostream>
#include <cmath>

using namespace std;

const int N=1010;
int n,m;
int a[N][N],dp[N][N];       //dp[i][j]表明以i,j为右下角的最大正方形边长
int ans;                    //最终最大边长

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];
            if(a[i][j]==0){
                dp[i][j]=0;         //如果该位置为0，则不可能构成正方形，且不会超过最大边长
                continue;
            }
            dp[i][j]=1;             //可能构成正方形的最小边长为1.
            if(i>0&&j>0){
                dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;    //避免大量重复计算
            }
            ans=max(ans,dp[i][j]);                  //确定最大边长
        }
    }
    cout<<ans*ans<<endl;            //输出面积
    return 0;
}