# Poj Solution 1371

```http://poj.org/problem?id=1371

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

using namespace std;

int x, y, xn, yn, n, m;

struct
{
int x1, x2, y1, y2;
}ln;

char map;

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;
}

```
This entry was posted in poj. Bookmark the permalink.