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