1371.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream>
#include <algorithm>
#include <memory.h>

using namespace std;

int x[200], y[200], xn, yn, n, m;

struct
{
	int x1, x2, y1, y2;
}ln[100];

char map[414][414];

bool init()
{
	int i, j, l, r, u, d, k;

	cin >> n;
	if( n == 0 ) return 0;

	xn = yn = 0;
	for( i=0; i<n; i++ )
	{
		cin >> ln[i].x1 >> ln[i].y1 >> ln[i].x2 >> ln[i].y2;

		x[ xn++ ] = ln[i].x1;	x[ xn++ ] = ln[i].x2;
		y[ yn++ ] = ln[i].y1;	y[ yn++ ] = ln[i].y2;
	}

	sort( x, x+xn );
	sort( y, y+yn );

	xn = std::unique_copy( x, x+xn, x ) - x;
	yn = std::unique_copy( y, y+yn, y ) - y;

	m = n * 4 + 4;

	for( i=0; i<m; i++ )
	for( j=0; j<m; j++ )
		map[i][j] = ' ';

	for( i=0; i<n; i++ )
	{
		l = 2 + ( std::lower_bound( x, x+xn, ln[i].x1 ) - x ) * 2;
		r = 2 + ( std::lower_bound( x, x+xn, ln[i].x2 ) - x ) * 2;
		u = 2 + ( std::lower_bound( y, y+yn, ln[i].y1 ) - y ) * 2;
		d = 2 + ( std::lower_bound( y, y+yn, ln[i].y2 ) - y ) * 2;

		if( l > r ) swap( l, r );
		if( u > d ) swap( u, d );

		for( j=l ; j <= r; j++ )
		for( k=u ; k <= d; k++ )
		{
			map[j][k] = '#';
		}
	}

	return 1;
}

int dx[]={ 0, 0, 1, -1 }, dy[]={ 1, -1, 0, 0 };

inline bool inmap( int x, int y )
{
	return 0 <= x && x < m && 0 <= y && y < m;
}

void fill( int x, int y, char wall, char past )
{
	int i, xx, yy;

	map[x][y] = past;
	for( i=0; i<4; i++ )
	if( inmap( xx=x+2*dx[i], yy=y+2*dy[i] ) && map[x+dx[i]][y+dy[i]] != wall && map[xx][yy] == ' ' )
		fill( xx, yy, wall, past );
}

void doit()
{
	int i, j, ans;

	fill( 1, 1, '#', '*' );

	ans = 0;
	for( i=1; i<m; i+=2 )
	for( j=1; j<m; j+=2 )
	if( map[i][j] == ' ' )
	{
		fill( i, j, '*', 'o' );
		ans ++ ;
	}

	cout<< ans << endl;
}

int main()
{
	while( init() )
		doit();

	return 0;
}