题目内容

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;
}
最后修改日期:2020年3月6日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。