洛谷P1387 最大正方形

题目链接

P1387 最大正方形

思路1：

前缀和+暴力，注意只有一个点时，边长记为1，而不是0.

#include 
#include
using namespace std;
int f[110][110],a[110][110];
int main(int argc, char** argv) {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);f[i][j]=a[i][j]+f[i-1][j]+f[i][j-1]-f[i-1][j-1];}}int maxv=min(n,m),flag=0,ans=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){for(int l=2;l<=maxv;l++){if(i+l-1>n||j+l-1>m)  continue;if((f[i+l-1][j+l-1]-f[i+l-1][j-1]-f[i-1][j+l-1]+f[i-1][j-1])==l*l){ans=max(ans,l);}}}}printf("%d\n",ans);return 0;
}

思路2：

动态规划，$f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1a[i]==1时$
其中$f[i][j]$表示从$(1,1)$到$(i,j)$最大的正方形的边长。

#include 
#include
using namespace std;
int f[110][110],a[110][110];
int n,m;
int main(int argc, char** argv) {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}int ans=1;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==1)f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;if(f[i][j]>ans)ans=f[i][j];}} printf("%d\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！