洛谷1169 [ZJOI2007] 棋盘制作

题目链接

题意概述：给出由0 1构成的矩阵，求没有0 1 相邻的最大子矩阵的最大子正方形。

解题思路：设f[i][j]表示i j向上能到哪，l[i][j] r[i][j]表示向左/右，转移时分开计算矩形和正方形即可。

#include<cstring>

#include<iostream>

#include<cctype>

#include<cstdio>

#include<algorithm>

using namespace std;

inline int read()

{

    register int X=;register char ch=;bool flag=;

    for(;!isdigit(ch);ch=getchar()) if(ch=='-') flag=;

    for(;isdigit(ch);ch=getchar()) X=(X<<)+(X<<)+ch-'';

    return (flag ? -X : X);

}

inline void write(int x)

{

     if(x>) write(x/);

     putchar(x%+'');

}

const int N=;

int l[N][N],r[N][N],f[N][N],n,m,a[N][N],ans1=,ans2=;

int min(const int x,const int y){return (x < y ? x : y);}

int max(const int x,const int y){return (x < y ? y : x);}

int main()

{

    n=read(),m=read();

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

            a[i][j]=read(),l[i][j]=r[i][j]=(j== ?  : j),f[i][j]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

            if(a[i][j] != a[i][j-])

                l[i][j]=l[i][j-];

        for(int j=m-;j>=;j--)

            if(a[i][j] != a[i][j+])

                r[i][j]=r[i][j+];

    }

    for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        {

            if(i >  && a[i][j] != a[i-][j])

                l[i][j]=max(l[i][j],l[i-][j]),r[i][j]=min(r[i][j],r[i-][j]),f[i][j]=f[i-][j]+;

            int k=r[i][j]-l[i][j]+,h=min(k,f[i][j]);

            ans1=max(ans1,k*f[i][j]);

            ans2=max(ans2,h*h);

        }

    write(ans2),putchar('\n'),write(ans1);

}