torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

AOJ 0531 : Paint Color

概要

$ H \times W $ の平面があり、平面上の $ N $ 個の領域が与えられる。
与えられた領域のいずれにも含まれない領域は、与えられた領域によって分割されている。
分割されている領域の数を求めよ。

解法

面積が大きいので、全てをメモリに格納しようとすると MLE してしまいます。
この問題の場合、重要なのは領域の数だけで、面積を計算する必要はないので、無駄な部分を省略することができます。
必要な部分は、各軸の方向に対して、変化のある部分とその前後の行または列だけです。
変化のある部分とは、入力によって与えられた点のある座標です。
$x$ 軸と $y$ 軸に分け、点が存在する部分の前後のみを抽出して平面を構築しなおします。
すると、高さと幅は高々 $ 3 \times N $ になるので、メモリに格納することができます。
あとは、よくある塗り潰しの全探索をすれば答えが求まります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int,int> PII;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )

#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )
#define MP( a, b ) make_pair( ( a ), ( b ) )

#define fst first
#define snd second

const int dir[][2] = {
	1, 0,
	0, 1,
	-1, 0,
	0, -1
};

// 座標圧縮
int comp( VI &x1, VI &x2, int W )
{
	const int N = x1.size();

	VI xs;

	REP( i, 0, N )
	{
		REP( j, -1, 2 )
		{
			// 変化のある座標の前後の座標について、有効な範囲なら追加

			int tmp1 = x1[i] + j, tmp2 = x2[i] + j;

			if ( 0 <= tmp1 && tmp1 < W )
			{
				xs.PB( tmp1 );
			}

			if ( 0 <= tmp2 && tmp2 < W )
			{
				xs.PB( tmp2 );
			}
		}
	}

	// 重複要素を消す
	sort( ALL( xs ) );
	xs.erase( unique( ALL( xs ) ), xs.end() );

	REP( i, 0, N )
	{
		// 新しい座標の取得
		
		x1[i] = lower_bound( ALL( xs ), x1[i] ) - xs.begin();
		x2[i] = lower_bound( ALL( xs ), x2[i] ) - xs.begin();
	}

	return xs.size();
}

// 矩形範囲を 1 で埋める
void paint( VVI &board, int x1, int y1, int x2, int y2 )
{
	REP( i, y1, y2 )
	{
		REP( j, x1, x2 )
		{
			board[i][j] = 1;
		}
	}

	return;
}

// BFS で塗り潰し
void bfs( VVI &board, int y, int x )
{
	const int H = board.size(), W = board[0].size();

	queue< PII > que;
	que.push( MP( y, x ) );

	while ( !que.empty() )
	{
		auto cur = que.front();
		que.pop();

		if ( board[ cur.fst ][ cur.snd ] )
		{
			continue;
		}

		board[ cur.fst ][ cur.snd ] = 1;

		REP( d, 0, 4 )
		{
			auto next = cur;

			next.fst += dir[d][0];
			next.snd += dir[d][1];

			if ( !( 0 <= next.fst && next.fst < H && 0 <= next.snd && next.snd < W ) )
			{
				continue;
			}

			que.push( next );
		}
	}

	return;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	while ( true )
	{
		int w, h;
		cin >> w >> h;

		if ( !( w | h ) )
		{
			break;
		}

		int n;
		cin >> n;

		VI x1( n ), y1( n ), x2( n ), y2( n );

		REP( i, 0, n )
		{
			cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
		}

		const int W = comp( x1, x2, w ), H = comp( y1, y2, h );

		VVI board( H, VI( W, 0 ) );

		REP( i, 0, n )
		{
			paint( board, x1[i], y1[i], x2[i], y2[i] );
		}

		int res = 0;

		REP( i, 0, H )
		{
			REP( j, 0, W )
			{
				if ( board[i][j] )
				{
					continue;
				}

				res++;

				bfs( board, i, j );
			}
		}

		cout << res << endl;
	}

	return 0;
}