Algorithm

USACO Section6.1 A Rectangular Barn (rectbarn)

Problem Summary

Given a N×M rectangular area with some 1×1 area damaged, find the biggest rectangular area without damages.

Solution

I used dynamic programming to solve this problem.
First, let:
height[i][j] be the maximum legal extension to the top of (i,j),
left[i][j] be the maximum legal extension to the left of (i,j),
right[i][j] be the maximum legal extension to the right of (i,j).
“legal extension” means the area from row i-height(i,j)+1 to row i, from column j-left[i][j]+1 to column j+right[i][j]-1 is available.

Then the answer is max{ height[i][j]*(left[i][j]+right[i][j]-1) }, 1<=i<=n,1<=j<=m.

Actually, we do not have to use two-dimensional arrays.
We can scan down row by row, and for each row, we can scan the columns and update the values of height[j] and left[j]. Then we scan the columns backwards and update the values of right[j].

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
const int maxn = 3002;
int n,m;
bool broken[maxn][maxn];
/* le:left.  ri:right */
int height[maxn],le[maxn],ri[maxn];
int main()
{
	fstream fin("rectbarn.in",ios::in);
	fstream fout("rectbarn.out",ios::out);
	int a,b,p;
	fin>>n>>m>>p;
	for(int i=0;i<p;i++)
	{
		fin>>a>>b;
		broken[a][b]=true;
	}
	int ans=0,k;
	for(int i=1;i<=n;i++)
	{
		k=0;
		for(int j=1;j<=m;j++)
		{
			if(broken[i][j])
				le[j]=height[j]=k=0;
			else
			{
				k++;
				if(le[j]==0) le[j]=k;
				else le[j]=min(k,le[j]);
				
				height[j]++;
			}
		}
		k=0;
		for(int j=m;j>=1;j--)
		{
			if(broken[i][j])
			{
				ri[j]=k=0;
				continue;
			}
			else
			{
				k++;
				if(ri[j]==0) ri[j]=k; 
				else ri[j]=min(k,ri[j]);
				
				ans=max(ans,height[j]*(le[j]+ri[j]-1));
			}
		}
	}
	fout<<ans<<endl;
	fin.close();
	fout.close();
	return 0;
}