AOJ-0531 : ペンキの色 ( Paint Color )

問題概要

[0,H)*[0,W)の中に軸に平行な長方形をN(<1000)個配置する。長方形でもとの領域がいくつに分割されるか求める問題。

解法

座標圧縮してflood fillすればよい。長方形を配置するのはいもす法を使う。

acceptされたコード

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct Rect {
	int x0, y0, x1, y1;

	Rect(){}
	Rect(int x0, int y0, int x1, int y1):
		x0(x0), y0(y0), x1(x1), y1(y1)
	{}
};

const int MAX_N = 1000;
int W, H, N;
int xs[2*MAX_N + 2], ys[2*MAX_N + 2];
Rect rects[MAX_N];
const int dy[] = {1,-1,0,0}, dx[] = {0,0,1,-1};
int board[2*MAX_N + 3][2*MAX_N + 3];

bool init() {
	scanf("%d%d", &W, &H);
	if (W == 0 && H == 0) {
		return false;
	}
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d%d%d%d", &rects[i].x0, &rects[i].y0, &rects[i].x1, &rects[i].y1);
		xs[2*i+0] = rects[i].x0;
		xs[2*i+1] = rects[i].x1;
		ys[2*i+0] = rects[i].y0;
		ys[2*i+1] = rects[i].y1;
	}
	xs[2*N+0] = 0;
	xs[2*N+1] = W;
	ys[2*N+0] = 0;
	ys[2*N+1] = H;

	sort(xs, xs + 2*N+2);
	sort(ys, ys + 2*N+2);

	int LX = 0, LY = 0;
	LX = unique(xs, xs + 2*N+2) - xs;
	LY = unique(ys, ys + 2*N+2) - ys;
	for (int i = 0; i < N; ++i) {
		rects[i].x0 = lower_bound(xs, xs + LX, rects[i].x0) - xs;
		rects[i].x1 = lower_bound(xs, xs + LX, rects[i].x1) - xs;
		rects[i].y0 = lower_bound(ys, ys + LY, rects[i].y0) - ys;
		rects[i].y1 = lower_bound(ys, ys + LY, rects[i].y1) - ys;
	}
	W = LX - 1;
	H = LY - 1;

	return true;
}

int solve() {
	memset(board, 0, sizeof(board));

	for (int i = 0; i < N; ++i) {
		++board[rects[i].y0][rects[i].x0];
		--board[rects[i].y1][rects[i].x0];
		--board[rects[i].y0][rects[i].x1];
		++board[rects[i].y1][rects[i].x1];
	}

	for (int i = 0; i < H; ++i) {
		board[i+1][0] += board[i][0];
	}
	for (int j = 0; j < W; ++j) {
		board[0][j+1] += board[0][j];
	}
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			board[i+1][j+1] += board[i+1][j] + board[i][j+1] - board[i][j];
		}
	}

	int ans = 0;
	vector< pair<int,int> > stack; stack.reserve(W*H);
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) if (board[i][j] == 0) {
			stack.clear();
			board[i][j] = 1;
			stack.push_back(make_pair(i, j));
			for (;!stack.empty();) {
				const int y = stack.back().first, x = stack.back().second;
				stack.pop_back();
				for (int k = 0; k < 4; ++k) {
					const int ny = y + dy[k], nx = x + dx[k];
					if ( 0 <= ny && ny < H && 0 <= nx && nx < W && board[ny][nx] == 0) {
						board[ny][nx] = 1;
						stack.push_back(make_pair(ny, nx));
					}
				}
			}
			++ans;
		}
	}
	return ans;
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}