[usaco]5.4.5 Big Barn题解

5
 
Big Barn

A Special Treat
Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided
into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal
or vertical axis.

EXAMPLE
Consider the following grid of Farmer John's land where `.' represents a parcel with no trees and `#' represents a parcel with trees:

          1 2 3 4 5 6 7 8
        1 . . . . . . . .
        2 . # . . . # . .
        3 . . . . . . . .
        4 . . . . . . . .
        5 . . . . . . . .
        6 . . # . . . . .
        7 . . . . . . . .
        8 . . . . . . . .

The largest barn is 5 x 5 and can be placed in either of two locations in the lower right part of the grid.

PROGRAM NAME: bigbrn
INPUT FORMAT
Line 1:  Two integers: N (1 <= N <= 1000), the number of parcels on a side, and T (1 <= T <= 10,000) the number of parcels with trees 

Lines 2..T+1: Two integers (1 <= each integer <= N), the row and column of a tree parcel 

SAMPLE INPUT (file bigbrn.in)
8 3
2 2
2 6
6 3

OUTPUT FORMAT
The output file should consist of exactly one line, the maximum side length of John's barn.

SAMPLE OUTPUT (file bigbrn.out)
5

--------------------------------------------------------------------------------

以前做过类似的题，所以这次特别的快。
算法很简单，记录每一个节点向左上方能够延伸出来的最大的方块的大小，以及能够向左延伸的最大距离，还有向上延伸的最大距离。
这样一来，如果某个节点是树木，那么这个节点的2个变量置0，否则left和up分别是上一个节点累加1，而squre取左上方一个节点+1，和left还有up相比较，取最小值，就是当前节点的squre。

还有个节省空间的办法，left，up还有squre三个矩阵并不需要n×n，因为有些行用过之后就没有用了，因此只需要保存两行就行了。

USER: Ma yunlei [yunleis2]
TASK: bigbrn
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4024 KB]
   Test 2: TEST OK [0.000 secs, 4024 KB]
   Test 3: TEST OK [0.000 secs, 4024 KB]
   Test 4: TEST OK [0.000 secs, 4024 KB]
   Test 5: TEST OK [0.000 secs, 4024 KB]
   Test 6: TEST OK [0.000 secs, 4024 KB]
   Test 7: TEST OK [0.000 secs, 4024 KB]
   Test 8: TEST OK [0.000 secs, 4024 KB]
   Test 9: TEST OK [0.000 secs, 4024 KB]
   Test 10: TEST OK [0.027 secs, 4024 KB]
   Test 11: TEST OK [0.027 secs, 4024 KB]
   Test 12: TEST OK [0.027 secs, 4024 KB]
   Test 13: TEST OK [0.027 secs, 4024 KB]
   Test 14: TEST OK [0.027 secs, 4024 KB]
   Test 15: TEST OK [0.027 secs, 4024 KB]

All tests OK.
YOUR PROGRAM ('bigbrn') WORKED FIRST TIME!  That's fantastic
-- and a rare thing.  Please accept these special automated
congratulations.

---------------------------------------------------------------------------

/*
ID:yunleis3
PROG:bigbrn
LANG:C++
*/

#include <fstream>
#include<iostream>

using namespace std;
const int maxn=1001;
const int maxt=10001;
bool metri[maxn][maxn];
int up[2][maxn];
int left1[2][maxn];
int squr[2][maxn];
int n,t;
int large=0;
#define rowindex(row)  ((row)%2)
#define min(x,y)   (x<y?x:y)
#define trimin(x,y,z)  (min(min(x,y),z))
int main()
{
	ifstream fin("bigbrn.in");
	fin>>n>>t;
	for(int i=0;i<t;++i){
		int a,b;
		fin>>a>>b;
		metri[a][b]=true;
	}
	for(int row=1;row<=n;++row){
		for(int col=1;col<=n;++col){
			if(metri[row][col]){
				up[rowindex(row)][col]=0;
				left1[rowindex(row)][col]=0;
				squr[rowindex(row)][col]=0;
			}else {
				up[rowindex(row)][col]=up[rowindex(row-1)][col]+1;
				left1[rowindex(row)][col]=left1[rowindex(row)][col-1]+1;
				squr[rowindex(row)][col]=trimin(up[rowindex(row)][col],left1[rowindex(row)][col],squr[rowindex(row-1)][col-1]+1);
				if(large<squr[rowindex(row)][col])
					large=squr[rowindex(row)][col];
			}
		}
	}
	ofstream fout("bigbrn.out");
	fout<<large<<endl;
	//system("pause");
}