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

我在51nod上面切的第一道8級題

我在51nod上面切的第一道8級題的一血

題目大意

有一個n*m的矩陣，矩陣中的每一個元素是'X'或者'.'，現(xiàn)在有若干次修改操作，每次修改操作是將某一個'.'改成'X'，修改之后要求計算出當(dāng)前矩陣?yán)锩嬷话?#39;.'的最大子方陣是多大，輸出方陣的邊長即可。

輸入

單組測試數(shù)據(jù)。
第一行有三個整數(shù)n, m 和 k(1<=n,m,k<=2000)，分別表示矩陣的大小和修改次數(shù)。
接下來n行，每一行有m個字符'X'或者'.'。
接下來k行，每一行有兩個整數(shù) xi, yi (1≤xi≤n, 1≤yi≤m)，表示所修改點的標(biāo)。
輸入保證所給的坐標(biāo)上面的字符一定是'.'。

輸出

輸出k行，對應(yīng)每次修改之后的最大子方陣的邊長。

題解

首先倒過來做，把加‘X’改成刪‘X’。

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

假如刪掉(x,y)處的‘X’答案變大了，那么答案矩陣顯然包括(x,y)

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

維護mal[x][y],mar[x][y]表示(x,y)向左向右能擴展到的最長距離。

那么假設(shè)新答案矩陣的上邊界為l，下邊界為r，保證左右寬度始終大于等于上下長度（即r-l 1）

l向下移的時候r肯定單調(diào)向下移。

所以復(fù)雜度是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]);
    }
}