AOJ 0531: Paint Color

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531


座標圧縮+二次元imos。

久しぶりに二次元imosしたけどこっちはうまくいった。座標圧縮で少しこんがらがった。
長方形の辺が存在しない区間の長さを1にする感じ。

int fd(const vector<int>& vec, int a) {
	return lower_bound(all(vec), a) - vec.begin();
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int H, W;
int N;
int C[MAX_N][MAX_N];
int X1[MAX_N], Y1[MAX_N], X2[MAX_N], Y2[MAX_N];

void solve() {
	while(true) {
		scanf("%d%d", &H, &W);
		if(H == 0 && W == 0) break;
		scanf("%d", &N);
		memset(C, 0, sizeof(C));
		vector<int> X, Y;
		X.push_back(0); X.push_back(H - 1);
		Y.push_back(0); Y.push_back(W - 1);
		rep(i, 0, N) {
			scanf("%d%d%d%d", &X1[i], &Y1[i], &X2[i], &Y2[i]);
			X2[i]--; Y2[i]--;
			X.push_back(X1[i]); X.push_back(X2[i]);
			Y.push_back(Y1[i]); Y.push_back(Y2[i]);
		}
		int nx = (int)X.size(), ny = (int)Y.size();
		rep(i, 0, nx - 1) if(X[i + 1] - X[i] != 1 && X[i] != H - 1) X.push_back((X[i] + 1));
		rep(i, 0, ny - 1) if(Y[i + 1] - Y[i] != 1 && Y[i] != W - 1) Y.push_back((Y[i] + 1));
		sort(all(X));
		sort(all(Y));
		X.erase(unique(all(X)), X.end());
		Y.erase(unique(all(Y)), Y.end());
		nx = X.size(); ny = Y.size();

		rep(i, 0, N) {
			int nx1 = fd(X, X1[i]); nx1++;
			int nx2 = fd(X, X2[i]); nx2++;
			int ny1 = fd(Y, Y1[i]); ny1++;
			int ny2 = fd(Y, Y2[i]); ny2++;
			C[nx2 + 1][ny2 + 1]++;
			C[nx1][ny2 + 1]--;
			C[nx2 + 1][ny1]--;
			C[nx1][ny1]++;
		}

		rep(i, 1, nx + 1) {
			rep(j, 1, ny + 1) {
				C[i][j] += C[i][j - 1] + C[i - 1][j] - C[i - 1][j - 1];
			}
		}
		
		queue<pi> que;
		int res = 0;
		rep(i, 1, nx + 1) {
			rep(j, 1, ny + 1) {
				if(C[i][j]) continue;
				que.push(pi(i, j));
				while(!que.empty()) {
					pi p = que.front(); que.pop();
					rep(i, 0, 4) {
						if(1 <= p.fst + dx[i] && p.fst + dx[i] <= nx
								&& 1 <= p.sec + dy[i] && p.sec + dy[i] <= ny) {
							if(!C[p.fst + dx[i]][p.sec + dy[i]]) {
								C[p.fst + dx[i]][p.sec + dy[i]] = 1;
								que.push(pi(p.fst + dx[i], p.sec + dy[i]));
							}
						}
					}
				}
				res++;
			}
		}
		cout << res << "\n";
	}
}

POJのせいでscanfとcoutが混ざってて草。