Poj Solution 1371

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