解题报告 P1681 最大正方形II

题目内容

P1681

大意：给定 0-1 矩阵，求最大交错正方形

解题思路

又是一道狗题目，其实观察性质后不难发现该题与最大正方形的思路很类似，令 f_{i,j} 表示以 (i,j) 为右下角的交错正方形的最大边长，有如下转移方程式：

f_{i,j}=\min_{a_{i,j}\neq a_{i-1,j}\land a_{i,j}\neq a_{i,j-1}}(f_{i-1,j-1},f_{i,j-1},f_{i-1,j})+1

理由和最大正方形的类似，最右下角的只可以继承边长最小的往左上角的正方形。并且一定要判定最后一个点是否交错。代码：

#include <cstdio>

inline int min(int a,int b)
{
    return a<b?a:b;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=1505;
int n,m,ans,a[maxn][maxn],f[maxn][maxn];

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            f[i][j]=1;
            scanf("%d",&a[i][j]);
            if(a[i][j]!=a[i-1][j] && a[i][j]!=a[i][j-1])
                f[i][j]=min(min(f[i-1][j-1],f[i-1][j]),f[i][j-1])+1;
            ans=max(f[i][j],ans);
        }
    printf("%d\n",ans);
    return 0;
}