首页 > 代码库 > BZOJ 1057 棋盘制作（最大黑白相间子矩阵）

BZOJ 1057 棋盘制作（最大黑白相间子矩阵）

2024-07-09 00:01:55   213人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1057

题意：给出一个只包含01的矩阵。找出一个01相间的最大的正方形子矩阵？找出一个01相间的最大的长方形子矩阵？

思路：一行一行扫描，对于某一行，记录每列 向上延伸的最大长度，记为h。然后再求出每列向右向左延伸的最大距离。比如2122345421，第4个位置的2向左延伸到3向右延伸到9。我们就是要求 出这个东西。我们用类似并查集思想。以向左为例。L[j]初始时指向j。从左向右扫描，对于j，令k=j-1，若（i,k）和(i,k+1)格子颜色不用 且h[k]>=h[j]，那么令L[j]=L[k]，接着令k=L[j]-1继续判断。我们求出这个L和R数组后只要再扫一遍，h[j]就是 高，R[j]-L[j]+1就是宽，更新答案即可。

 

int n,m,g[N][N],h[N];int Max,MAX;void deal(){    clr(h,0);    int i,j,k,left,right,L[N],R[N],x,y;    FOR0(i,n)    {        FOR0(j,m)        {            if(i==0||g[i][j]==g[i-1][j]) h[j]=1;            else h[j]++;        }        FOR0(j,m) L[j]=R[j]=j;        FOR1(j,m-1)        {            k=j-1;            while(k>=0&&h[k]>=h[j]&&g[i][k]!=g[i][k+1])            {                L[j]=L[k];                k=L[j]-1;            }        }        FORL0(j,m-2)        {            k=j+1;            while(k<=m-1&&h[k]>=h[j]&&g[i][k]!=g[i][k-1])            {                R[j]=R[k];                k=R[j]+1;            }        }        FOR0(j,m)        {            x=h[j]; y=R[j]-L[j]+1;            if(x>y) swap(x,y);            if(x==y)            {                if(x*y>MAX) MAX=x*y;                if(y*x-x>Max) Max=y*x-x;            }            else            {                if(x*y>Max) Max=x*y;                else if(x*x>MAX) MAX=x*x;            }        }    }}int main(){    RD(n,m);    int i,j;    FOR0(i,n) FOR0(j,m) RD(g[i][j]);    deal();    PR(MAX);    PR(Max);    return 0;}

 

 

 


联系
我们