第7回 JOI2008 日本情報オリンピック 本選 「ペンキの色」

座標圧縮 is 楽しい
趣味は座標圧縮です。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
int w,h,n,d[1004][4],so[2];
int m[2010][2010];
int kari[2][6010];
int di[4] = {-1,0,1,0};
int dj[4] = {0,-1,0,1};
int sea(int ban,int s){
	int lb = 0,ub = so[ban]+1;
	while(ub - lb > 1){
		int mid = (ub + lb)/2;
		if(kari[ban][mid] <= s) lb = mid;
		else ub = mid;
	}
	if(kari[ban][max(0,lb-1)] == s)return max(0,lb-1);
	if(kari[ban][lb+1] == s)return lb+1;
	if(kari[ban][lb] != s)cout << "pou" << endl;
	return lb;
}

int main(){
	while(1){
		scanf("%d%d",&w,&h);
		if(w + h == 0)break;
		scanf("%d",&n);
		so[0] = 0;
		so[1] = 0;
		w *= 2;
		h *= 2;

		for(int i = 0;i < 2010;i++){
			for(int j = 0;j < 2010;j++){
				m[i][j] = 0;
			}
		}
		int co[2] = {0};
		for(int i = 0;i < n;i++){
			for(int j = 0;j < 4;j++){
				scanf("%d",&d[i][j]);
				d[i][j] *= 2;
				for(int k = -1;k <= 1;k++){
					if(d[i][j] == 0 && k == -1)continue;
					if(j%2 == 0 && d[i][j] + k > w)continue;
					if(j%2 == 1 && d[i][j] + k > h)continue;
					kari[j%2][co[j%2]++] = d[i][j]+k;//追加わんちゃん
				}
			}
		}
		for(int i = 0;i < 2;i++){
			if(co[i] == 0)continue;
			sort(kari[i],kari[i] + co[i]);
		}

		int len[2];
		for(int i = 0;i < 2;i++)len[i] = co[i];
		for(int ban = 0;ban < 2;ban++){
			so[ban]++;
			for(int i = 1;i < len[ban];i++){
				if(kari[ban][i-1] != kari[ban][i]){
					kari[ban][so[ban]++] = kari[ban][i];
				}
			}
		}

		for(int i = 0;i < n;i++){
			int x1 = sea(0,d[i][0]);
			int x2 = sea(0,d[i][2]);
			int y1 = sea(1,d[i][1]);
			int y2 = sea(1,d[i][3]);

			for(int j = x1;j <= x2;j++){
				m[y1][j]++;
				m[y2+1][j]--;
			}
		}
		for(int i = 1;i < so[1];i++){
			for(int j = 0;j < so[0];j++){
				m[i][j] += m[i-1][j];
				if(i > 2){
					if(m[i-2][j] > 0)m[i-2][j] = 1;
				}
			}
		}
		int ans = 0;
		queue<P> que;
		for(int i = 0;i < so[1];i++){
			for(int j = 0;j < so[0];j++){
			//	queue<P> que;
				if(m[i][j] == 0)que.push(P(i,j)),ans++;
				while(que.size()){
					P q = que.front(); que.pop();
					int ii = q.first;
					int jj = q.second;
					for(int z = 0;z < 4;z++){
						int ni = ii + di[z];
						int nj = jj + dj[z];
						if(ni >= 0 && ni < so[1] && nj >= 0 && nj < so[0] && m[ni][nj] == 0)que.push(P(ni,nj)),m[ni][nj]=-1;
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}