题目内容

P1736

大意:求给定 0-1 矩阵中最大的只有对角线为 1 的正方形子矩阵的边长

解题思路

由于第一眼没看清题,没注意到子矩阵仅有对角线为 1,结果只对了两个点。(血的教训)

然后调试无果,看了题解,发现这题和最大正方形很像,然后就 AC 了。

思路:和最大正方形相似,一开始进行预处理:s1[i][j] 表示这个点左方/右方最多有几个连续的 0,s2[i][j] 表示这个点上方最多有几个连续的 0,然后设 f[i][j] 表示以 (i,j) 为右下角的满足题意的正方形的最大边长,然后转移方程如下:

//第一轮,求解左上->右下的对角线
f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;
//第二轮,求解右上->左下的对角线
f[i][j]=min(f[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1;

代码:

#include <cstdio>
#include <cstring>

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

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

const int maxn=2505;
int n,m,a[maxn][maxn],f[maxn][maxn],s1[maxn][maxn],s2[maxn][maxn],ans;

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)//第一轮
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            if(!a[i][j])//预处理 s 数组
            {
                s1[i][j]=s1[i][j-1]+1;
                s2[i][j]=s2[i-1][j]+1;
            }
            if(a[i][j])
                f[i][j]=min(f[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1;
            ans=max(ans,f[i][j]);
        }
    memset(f,0,sizeof(f));
    memset(s1,0,sizeof(s1));
    for(int i=1;i<=n;i++)//第二轮处理
        for(int j=m;j>=1;j--)
        {
            if(!a[i][j])
                s1[i][j]=s1[i][j+1]+1;
            if(a[i][j])
                f[i][j]=min(f[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1;
            ans=max(ans,f[i][j]);
        }
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年3月6日

作者

留言

撰写回覆或留言

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