【巧妙预处理系列】【UVA1330】City game

最大子矩阵（City Game, SEERC 2004, LA 3029）

给定一个m×n的矩阵，其中一些格子是空地（F），其他是障碍（R）。找出一个全部由F组成的面积最大的子矩阵，输出其面积乘以3后的结果。

【输入格式】

输入的第一行为数据组数T。每组数据的第一行为整数m和n（1≤m,n≤1 000）；以下m行每行n个字符（保证为F或者R），即输入矩阵。

【输出格式】

对于每组数据，输出面积最大的、全由F组成的矩阵的面积乘以3后的结果。

Sample Input

2

5 6

R F F F F F

F F F F F F

R R R F F F

F F F F F F

F F F F F F

5 5

R R R R R

R R R R R

R R R R R

R R R R R

R R R R R

Sample Output

45

0

自己实在没有一点思路

所以直接贴题解了

【分析】

最容易想到的算法便是：枚举左上角坐标和长、宽，然后判断这个矩形是否全为空地。这样做需要枚举O(m²n²)个矩形，判断需要O(mn)时间，总时间复杂度为O(m³n³)，实在是太高了。本题虽然是矩形，但仍然可以用扫描法：从上到下扫描。

我们把每个格子向上延伸的连续空格看成一条悬线，并且用up(i,j)、left(i,j)、right(i,j)表示格子(i,j)的悬线长度以及该悬线向左、向右运动的“运动极限”，如图1-30所示。列3的悬线长度为3，向左向右各能运动一列，因此左右的运动极限分别为列2和列4。

图 1-30

这样，每个格子(i,j)对应着一个以第i行为下边界、高度为up(i,j)，左右边界分别为left(i,j)和right(i,j)的矩形。不难发现，所有这些矩形中面积最大的就是题目所求（想一想，为什么）。这样，我们只需思考如何快速计算出上述3种信息即可。

当第i行第j列不是空格时，3个数组的值均为0，否则up(i,j)=up(i-1,j)+1。那么，left和right呢？深入思考后，可以发现：

left(i,j) = max{left(i-1,j), lo+1}

其中lo是第i行中，第j列左边的最近障碍格的列编号。如果从左到右计算left(i,j)，则很容易维护lo。right也可以同理计算，但需要从右往左计算，因为要维护第j列右边最近的障碍格的列编号ro。为了节约空间，下面的程序用up[j]，left[j]和right[j]来保存当前扫描行上的信息。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define maxn 1010

using namespace std;

int n,m;

char map[maxn][maxn];

int up[maxn][maxn];

int Left[maxn][maxn];

int Right[maxn][maxn];

int ans;

void input()

{

	memset(up,0,sizeof(up));

	memset(Left,0,sizeof(Left));

	memset(Right,0,sizeof(Right));

	cin>>n>>m;

	for(int i=1;i<=n;i++)

	 {

		getchar();

	 	for(int j=1;j<=m;j++)

		{

			map[i][j]=getchar();

			if(map[i][j]!='R'&&map[i][j]!='F') j--;

		}

	}

	for(int j=1;j<=m;j++)

	Left[0][j]=Right[0][j]=99999999;

	getchar();

}

void solve()

{

	for(int i=1;i<=n;i++)

	 {

		 int  temp=0;

	 	for(int j=1;j<=m;j++)

			{

				if(map[i][j]!='R')

			 	{

			 		up[i][j]=up[i-1][j]+1;

			 		Left[i][j]=min(Left[i-1][j],j-temp-1);

			 		if(map[i-1][j]=='R') Left[i][j]=j-temp-1;

				 }

				else

				{

					temp=j;

				}

			}

			temp=m+1;

		for(int j=m;j>=1;j--)

			{

				if(map[i][j]!='R')

				{

					Right[i][j]=min(Right[i-1][j],temp-j-1);

					if(map[i-1][j]=='R') Right[i][j]=temp-j-1;

				}

				else

				{

					temp=j;

				}

			}

	}

	ans=0;

	for(int i=1;i<=n;i++)

	 for(int j=1;j<=m;j++)

	 {

	 	 ans=max(ans,(up[i][j])*(Right[i][j]+Left[i][j]+1));

	 }

}

int main()

{

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	int N;

	cin>>N;

	while(N--)

	{

		input();

		solve();

		cout<<ans*3<<endl;

	}

}

巴特西

【巧妙预处理系列】【UVA1330】City game

Sample Input

Sample Output

最新文章

热门文章