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が混ざってて草。