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

	}

}