AOJ 0531 Paint Color
解法
座標圧縮→dfs(bfs)で領域を埋めていく
座標圧縮しないと、配列でベニヤ板の領域分取ることはできない
ソースコード
#define FOR(i, a, b) for (int i = (a);i < (b); ++i) #define REP(i, n) FOR(i, 0, n) int w, h, n; int X, Y; bool field[1024][1024]; void mp(map<int, int>& a, vector<int>& b) { sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); REP(i, b.size()) a[b[i]] = i; return; } void paint(int y, int x) { field[y][x] = true; REP(i, 4) { int dx = x + DI[i], dy = y + DJ[i]; if(0 <= dx && dx < X && 0 <= dy && dy < Y && !field[dy][dx]) { paint(dy, dx); } } return; } int main() { int x1[1024], y1[1024], x2[1024], y2[1024]; while(~scanf("%d%d", &w, &h) && w) { memset(field, 0, sizeof field); int res = 0; vector<int> x, y; map<int, int> x_aft, y_aft; scanf("%d", &n); REP(i, n) { scanf("%d%d%d%d", x1+i, y1+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]); } x.push_back(0); x.push_back(w); y.push_back(0); y.push_back(h); mp(x_aft, x); mp(y_aft, y); X = x.size(); Y = y.size(); REP(i,Y) REP(j,X) field[i][j] = (i == Y - 1 || j == X - 1); REP(i, n) FOR(j, y_aft[y1[i]], y_aft[y2[i]]) FOR(k, x_aft[x1[i]], x_aft[x2[i]]) field[j][k] = true; REP(i, Y) REP(j, X) if(!field[i][j]) { paint(i, j); res++; } printf("%d\n", res); } }