51nod1787最大子方阵

我在51nod上面切的第一道题

我在51nod上面切的第一道8级题

我在51nod上面切的第一道8级题的一血

题目大意

有一个n*m的矩阵，矩阵中的每一个元素是'X'或者'.'，现在有若干次修改操作，每次修改操作是将某一个'.'改成'X'，修改之后要求计算出当前矩阵里面只包含'.'的最大子方阵是多大，输出方阵的边长即可。

输入

单组测试数据。
第一行有三个整数n, m 和 k(1<=n,m,k<=2000)，分别表示矩阵的大小和修改次数。
接下来n行，每一行有m个字符'X'或者'.'。
接下来k行，每一行有两个整数 xi, yi (1≤xi≤n, 1≤yi≤m)，表示所修改点的标。
输入保证所给的坐标上面的字符一定是'.'。

输出

输出k行，对应每次修改之后的最大子方阵的边长。

题解

首先倒过来做，把加‘X’改成删‘X’。

最初的答案可以二分答案求

假如删掉(x,y)处的‘X’答案变大了，那么答案矩阵显然包括(x,y)

于是考虑求包含(x,y)的最大合法子矩阵。

维护mal[x][y],mar[x][y]表示(x,y)向左向右能扩展到的最长距离。

那么假设新答案矩阵的上边界为l，下边界为r，保证左右宽度始终大于等于上下长度（即r-l+1）

l向下移的时候r肯定单调向下移。

所以复杂度是O(\(n^2\))的

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,k,i,l,r,mid,x,y;
char map[2005][2005];
int sum[2005][2005];
int mal[2005][2005],mar[2005][2005];
int exl[2005],exr[2005];
int q[2005][2];
int ans[2005];

void preprocess()
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            if (map[i][j]=='X')
            sum[i][j]++;
        }
    }
}

int pd(int len)
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if ((i+len-1>n)||(j+len-1>m)) continue;
            if (sum[i+len-1][j+len-1]-sum[i-1][j+len-1]-sum[i+len-1][j-1]+sum[i-1][j-1]==0) return 1;
        }
    }
    return 0;
}

int getans()
{
    preprocess();
    if (sum[n][m]==n*m) return 0;
    l=1;
    r=min(n,m);
    mid=(l+r+1)/2;
    while (l<r)
    {
        if (pd(mid)==1)
            l=mid;
        else
            r=mid-1;
        mid=(l+r+1)/2;
    }
    return mid;
}

int update(int x)
{
    int y;
    for (y=1;y<=m;y++)
    {
        if (map[x][y]=='X') mal[x][y]=0;
        else mal[x][y]=mal[x][y-1]+1;
    }
    for (y=m;y>=1;y--)
    {
        if (map[x][y]=='X') mar[x][y]=0;
        else mar[x][y]=mar[x][y+1]+1;
    }
}

int main()
{
    freopen("read.in","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++)
    {
        scanf("%s",map[i]+1);
    }
    for (i=1;i<=k;i++)
    {
        scanf("%d%d",&q[i][1],&q[i][2]);
        map[q[i][1]][q[i][2]]='X';
    }
    ans[k]=getans();
    for (i=1;i<=n;i++)
    {
        update(i);
    }
    for (i=k;i>=1;i--)
    {
        x=q[i][1];
        y=q[i][2];
        map[x][y]='.';
        update(x);
        exl[x]=mal[x][y];
        exr[x]=mar[x][y];
        for (l=x-1;l>=1;l--)
        {
            exl[l]=min(exl[l+1],mal[l][y]);
            exr[l]=min(exr[l+1],mar[l][y]);
        }
        for (r=x+1;r<=n;r++)
        {
            exl[r]=min(exl[r-1],mal[r][y]);
            exr[r]=min(exr[r-1],mar[r][y]);
        }
        r=x;
        for (l=1;l<=x;l++)
        {
            while ((r+1<=n)&&(min(exl[l],exl[r+1])+min(exr[l],exr[r+1])-1>=r-l+1))
            {
                r++;
            }
            if (min(exl[l],exl[r])+min(exr[l],exr[r])-1>=r-l+1)
            ans[i-1]=max(ans[i-1],r-l+1);
        }
        ans[i-1]=max(ans[i-1],ans[i]);
    }
    for (i=1;i<=k;i++)
    {
        printf("%d\n",ans[i]);
    }
}