解题报告 P1736 创意吃鱼法

题目内容

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