AOJ Problem 0531 : Paint Color

404 Not Found

座標圧縮(xとy別々にやる。蟻本の考え方通り、出てくる座標の直前直後含め3マスだけ取れば良いとしてやる)。今まで座標圧縮とか恐いと思って手を出していなかったが、意外に実装は重くなかった。"やり方さえ間違えなければ"。

まあ一度実際に組むと実装方法忘れない気がするので良しとする。

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(n) n.begin(),n.end()
struct P{
	int x,y;
	P(int a,int b){x=a,y=b;}
};

// org = 本来出現する座標つめあわせ　, length = サイズ(縦or横) , 圧縮の結果に基づいて座標を更新する書き込み先 &one , &two .
int compress(vector<int> &org,int length,vector<int> &one,vector<int> &two){
	//ソートしておく。あと座標の重複も除く。
	sort(all(org));
	org.erase(unique(all(org)),org.end());
	
	int cur = 0;
	for(int i=(org[0]==0?1:0);i<org.size();i++){ //org[0]が0だったら被る(それはこまるので0の時org[1]からはじまる)。
		if(org[i] == cur+1) cur += 1; //隣接してたら1つだけずらす。
		else cur += 2;	//隣接してないんだったら2つ(1つ間が空くように取るよ)
		rep(j,one.size()) if(one[j] == org[i]) one[j] = cur;
		rep(j,two.size()) if(two[j] == org[i]) two[j] = cur;
	}
	return cur + (org.back()!=length); // org.back() !- lengthだった場合空間にまだ余裕があるのでサイズはlength = cur+1とする。
}


void dfs(bool Map[2000][2000],P start,int W,int H){
	static const int dx[] = {0,0,-1,1} , dy[] = {1,-1,0,0};
	
	stack<P> S;
	S.push(start);
	while(S.size()){
		P s = S.top(); S.pop();
		rep(i,4){
			P t = P(s.x+dx[i],s.y+dy[i]);
			if(t.y >= 0 && t.x >= 0 && t.y < H && t.x < W && Map[t.y][t.x] == 0){
				Map[t.y][t.x] = true;
				S.push(t);
			}
		}
	}
}


bool board[2000][2000];
int main(){
	int W,H;
	while(cin >> W >> H , W){
		vector<int> ox,oy,sx,ex,sy,ey;
		int n; cin >> n;
		rep(i,n){
			int x1,y1,x2,y2;
			cin >> x1 >> y1 >> x2 >> y2;			
			sx.push_back(x1),sy.push_back(y1); //s = 左下 (座標圧縮される方1)
			ex.push_back(x2),ey.push_back(y2); //e = 右上 (座標圧縮される方2)
			
			ox.push_back(x1),oy.push_back(y1); //o = sもeもどっちもつっこむ。(座標圧縮の目印に使う)
			ox.push_back(x2),oy.push_back(y2); //
		}
		// 圧縮 compress(...)の返り値は圧縮後の盤面サイズ。
		W = compress(ox,W,sx,ex);
		H = compress(oy,H,sy,ey);
		
		
		rep(i,H)rep(j,W)board[i][j] = false; // 初期化
		
		//圧縮後の左下と右上座標を使って盤面を塗りつぶす。
		rep(i,n){
			for(int x = sx[i] ; x < ex[i] ; x++){
				for(int y = sy[i] ; y < ey[i] ; y++){
					board[y][x] = true;
				}
			}
		}
		//塗りつぶしながら数える感じ。実際に塗りつぶすのはdfs()関数。
		int ans = 0;
		rep(y,H){
			rep(x,W){
				if(board[y][x] == false){
					ans++;
					dfs(board,P(x,y),W,H);
				}
			}
		}
		
		cout << ans << endl;
	}
}