http://poj.org/problem?id=1371
#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;
}