P1681 最大正方形II

Captain_Paul

2017-10-09 20:19:37

Solution

##小蒟蒻来发题解啦。。 //这道题和最大正方形1类似,不同之处在于对正方形的要求 //与最大正方形1相同,我们可以用f[i][j]来表示以(i,j)为右下角的正方形边长 //我们从(1,1)开始读入,那么,只要a[i][j]与a[i-1][j],a[i][j-1]都不相同,就可以列出状态转移方程: ```cpp //f[i][j]=min(f[i-1][j-1],min(f[i][j-1],f[i-1][j])) //特殊地,对于左上角的数,需要一个小处理,即:a[0][1]和a[1][0]都要与a[1][1]不同 //话不多说,上代码: #include<iostream> #include<cstdio> using namespace std; int n,m,ans,a[1501][1501],f[1501][1501]; int main() { int i,j; scanf("%d%d",&n,&m); for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%d",&a[i][j]); if (a[1][1]) a[1][0]=a[0][1]=0; else a[1][0]=a[0][1]=1; for (i=1;i<=n;i++) for (j=1;j<=m;j++) if (a[i][j]==0&&a[i-1][j]==1&&a[i][j-1]==1) f[i][j]=min(f[i-1][j-1],min(f[i][j-1],f[i-1][j]))+1; else if (a[i][j]==1&&a[i-1][j]==0&&a[i][j-1]==0) f[i][j]=min(f[i-1][j-1],min(f[i][j-1],f[i-1][j]))+1; for (i=1;i<=n;i++) for (j=1;j<=m;j++) ans=max(ans,f[i][j]); printf("%d\n",ans+1); return 0; } ```