题解：P1387 最大正方形

lg12321a · 2025-12-16 17:53:42 · 题解

思路

蒟蒻不会二分，但居然会动态规划，所以就用动态规划来做这道题了。

我们将每个点作为正方形的右下角来看待。

根据上面的内容可以推出状态转移方程: :::align{center} dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1; :::

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[105][105],n,m,a[105][105],ans; 
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==1){
                dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            ans=max(ans,dp[i][j]);
        }
    }
    cout<<ans;
    return 0;
}