P1681 最大正方形II

2017-10-09 20:19:37


小蒟蒻来发题解啦。。

//这道题和最大正方形1类似,不同之处在于对正方形的要求

//与最大正方形1相同,我们可以用f[i][j]来表示以(i,j)为右下角的正方形边长

//我们从(1,1)开始读入,那么,只要a[i][j]与a[i-1][j],a[i][j-1]都不相同,就可以列出状态转移方程:

//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;
}