51nod1787最大子方阵

痛定思痛。 2023-08-17 15:35 127阅读 0赞

# 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]);
        }
    }

转载于:https://www.cnblogs.com/leason-lyx/p/11515357.html