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; }