AOJ_0531 Paint Color

解法
座標圧縮+DFS
はじめて座標圧縮した。
解説を参考にして解いた

#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int MAX_N = 1000;
int N, h, w;
bool a[MAX_N * 2 + 3][MAX_N * 2 + 3];

int dx[4] = { 1, -1, 0, 0};
int dy[4] = { 0, 0,  1, -1};
void dfs(int x, int y){
	a[x][y] = true;
	for(int i = 0; i < 4; i++){
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(!a[nx][ny] && 0 <= nx && nx < w && 0 <= ny && ny < h){
			dfs(nx, ny);
		}
	}
	return;
}

int main(){
	while(scanf("%d %d", &w, &h) && h != 0){
		scanf("%d", &N);
		int x1[N+1], y1[N+1], x2[N+1], y2[N+1];
		set<int> setx;
		set<int> sety;
		setx.insert(w); setx.insert(0);
		sety.insert(h);	sety.insert(0);
		x1[0] = 0; y1[0] = 0; x2[0] = w; y2[0] = h;
		for(int i = 1; i <= N; i++){
			scanf("%d %d %d %d", &x1[i], &y1[i], &x2[i], &y2[i]);
			setx.insert(x1[i]); setx.insert(x2[i]);
			sety.insert(y1[i]); sety.insert(y2[i]);
		}
		set<int>::iterator it = setx.begin();
		for(int i = 0; it != setx.end(); i++){
			for(int j = 0; j <= N; j++){
				if(x1[j] == *it) x1[j] = i;
				if(x2[j] == *it) x2[j] = i;
			}
			it++;
		}
		it = sety.begin();
		for(int i = 0; it != sety.end(); i++){
			for(int j = 0; j <= N; j++){
				if(y1[j] == *it) y1[j] = i;
				if(y2[j] == *it) y2[j] = i;
			}
			it++;
		}

		//塗りつぶし
		w = x2[0]; h = y2[0];
		for(int i = 0; i < w; i++){
			for(int j = 0; j < h; j++){
				a[i][j] = false;
			}
		}
		for(int i = 1; i <= N; i++){
			for(int x = x1[i]; x < x2[i]; x++){
				for(int y = y1[i]; y < y2[i]; y++){
					a[x][y] = true;
				}
			}
		}

		int ans = 0;
		for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
				if(!a[j][i]){
					ans++;
					dfs(j, i);
				}
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}