玉蟾宮---懸線法之算法2

題目描述 Description

有一天，小貓rainbow和freda來到了湘西張家界的天門山玉蟾宮，玉蟾宮宮主藍兔盛情地款待了它們，并賜予它們一片土地。

這片土地被分成N*M個格子，每個格子裡寫着’R’或者’F’，R代表這塊土地被賜予了rainbow，F代表這塊土地被賜予了freda。

　　現在freda要在這裡賣萌。。。它要找一塊矩形土地，要求這片土地都标着’F’并且面積最大。

　　但是rainbow和freda的OI水準都弱爆了，找不出這塊土地，而藍兔也想看freda賣萌（她顯然是不會程式設計的……），是以它們決定，如果你找到的土地面積為S，它們每人給你S兩銀子。

輸入描述 Input Description

　　第一行兩個整數N,M，表示矩形土地有N行M列。

　　接下來N行，每行M個用空格隔開的字元’F’或’R’，描述了矩形土地。

輸出描述 Output Description

　　輸出一個整數，表示你能得到多少銀子，即(3*最大’F’矩形土地面積)的值。

樣例輸入 Sample Input

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

樣例輸出 Sample Output

45

資料範圍及提示 Data Size & Hint

　　對于50%的資料，1<=N,M<=200

　　對于100%的資料，1<=N,M<=1000

來源：Nescafe 20

分析

标準的最大子矩陣，将‘R’視為障礙點，即‘1’，‘F’視為‘0’，所求即為最大全0子矩陣。這裡選用懸線法的算法2。

思路

1. 對于底部為(i,j)的懸線：

   hight[i,j]：高 (向上延伸長度)

   left[i,j]：向左延伸的長度

   right[i,j]：向右延伸的長度

2. 預處理

   a[i,j]為障礙點：hight[i,j]=0，left[i,j]=0,right[i,j]=0

   a[i,j]不為障礙點：(1->m)hight[i,j]=hight[i-1,j]+1，left[i,j]=left[i,j-1]+1，(m->1)right[i,j]=right[i,j+1]+1;

3. 轉移

   h[i][j]>1： l[i][j]=min(l[i][j],l[i-1][j]); r[i][j]=min(r[i][j],r[i-1][j]);

   {l[i][j] 和 r[i][j] 的值都各自取決于 l[i-1][j] 和 r[i-1][j], 保證是一個矩形}

4. 計算答案

   ans=(l[i][j]+r[i][j]-1)*h[i][j]

代碼

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define close fclose(stdin); fclose(stdout);

int n,m;
int ans;
bool a[1005][1005];
int l[1005][1005];
int r[1005][1005];
int h[1005][1005];

int max(int x,int y)
{
	return x>y?x:y;
}
int min(int x,int y)
{
	return x<y?x:y;
}

int main()
{
	open("2491");  //codevs

	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	{
		char c=getchar();
		for(;c!='R' && c!='F';c=getchar());
		if(c=='R') a[i][j]=1;
	}
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	{
	    if(!a[i][j])
		{
			h[i][j]=h[i-1][j]+1;
			l[i][j]=l[i][j-1]+1;
		}
		if(!a[i][m-j+1])  // 從m至1
			r[i][m-j+1]=r[i][m-j+2]+1;
	}
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	if(h[i][j])
	{
		if(h[i][j]>1)
		{
			l[i][j]=min(l[i-1][j],l[i][j]);
			r[i][j]=min(r[i-1][j],r[i][j]);
		}
		ans=max(ans,(r[i][j]+l[i][j]-1)*h[i][j]);
	}
	printf("%d",3*ans);
	close;
	return 0;
}