JOI2008本選 問題5@C++(-31)

やっとできたーーーーーーーーーーーっ!

いやこれを本番で解くとか不可能だろ。

どんだけ必死だったかはソース見ればわかるので多くを語らない。コメント付けたから読めると思う。

/*
TASKNO: 5
LANG: C++
NAME: Masaki Hara J
*/

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>

//座標圧縮を行わないオプション
//#define NO_COMP
//デバッグ用出力のオプション
//#define DEBUG_PRINT

using namespace std;

int main(int argc,char* argv[])
{
	//ファイルを開く。
	FILE* in=fopen(argc>1?argv[1]:"input.txt","r");
	FILE* out=fopen(argc>2?argv[2]:"output.txt","w");
	int real_w,real_h,n;
	fscanf(in,"%d %d\n",&real_w,&real_h);
	fscanf(in,"%d\n",&n);
	#ifdef DEBUG_PRINT
	printf("real_w=%d,real_h=%d,n=%d\n",real_w,real_h,n);
	#endif
	//外壁用スペースの確保
	real_w+=2;
	real_h+=2;
	//座標圧縮用ハッシュ。差分状態で保持して後で和分する。
	vector<int> rtov_x(real_w+1);
	vector<int> rtov_y(real_h+1);
	//矩形を格納
	vector<pair<pair<int,int>,pair<int,int> > > rects(n+4);
	//使用する座標のrtovを1にする作業
	//外壁用の座標を確保
	rtov_x[0]++;
	rtov_y[0]++;
	rtov_x[1]++;
	rtov_y[1]++;
	rtov_x[real_w-1]++;
	rtov_y[real_h-1]++;
	rtov_x[real_w]++;
	rtov_y[real_h]++;
	//矩形で使用する座標を確保
	for(int i=0;i<n;i++) {
		int& x1=rects[i].first.first;
		int& y1=rects[i].first.second;
		int& x2=rects[i].second.first;
		int& y2=rects[i].second.second;
		fscanf(in,"%d %d %d %d\n",&x1,&y1,&x2,&y2);
		x1++;y1++;x2++;y2++;
		if(x1>x2)swap(x1,x2);
		if(y1>y2)swap(y1,y2);
		if(rtov_x[x1]==0) rtov_x[x1]++;
		if(rtov_x[x2]==0) rtov_x[x2]++;
		if(rtov_y[y1]==0) rtov_y[y1]++;
		if(rtov_y[y2]==0) rtov_y[y2]++;
	}
	#ifdef NO_COMP
	for(int x=0;x<real_w+1;x++) {rtov_x[x]=x;}int width=real_w;
	for(int y=0;y<real_h+1;y++) {rtov_y[y]=y;}int height=real_h;
	#else /* NO_COMP */
	//rtovを和分することで、座標ハッシュとして機能させる
	//例
	//1,1,0,1,1,0,0,0,0,0,0,1,1, から
	//0,1,1,2,3,3,3,3,3,3,3,4,5, にする
	//virtual_x = rtov_x[real_x] となる
	int subsum=0;
	for(int x=0;x<real_w+1;x++) {subsum+=rtov_x[x];rtov_x[x]=subsum-1;}int width=subsum-1;
	subsum=0;
	for(int y=0;y<real_h+1;y++) {subsum+=rtov_y[y];rtov_y[y]=subsum-1;}int height=subsum-1;
	#endif /* NO_COMP */
	
	#ifdef DEBUG_PRINT
	for(int x=0;x<real_w+1;x++) {printf("%d,",rtov_x[x]);}printf("\n");
	for(int y=0;y<real_h+1;y++) {printf("%d,",rtov_y[y]);}printf("\n");
	printf("width=%d,height=%d\n",width,height);
	#endif /* DEBUG_PRINT */
	
	//マスキングテープの枚数を表すマップ。
	//こちらも、差分状態で作成して、あとから和分する
	vector<vector<int> > paper_map(width+1,vector<int>(height+1));
	for(int i=0;i<n;i++) {
		int x1=rtov_x[rects[i].first.first];
		int y1=rtov_y[rects[i].first.second];
		int x2=rtov_x[rects[i].second.first];
		int y2=rtov_y[rects[i].second.second];
		#ifdef DEBUG_PRINT
		printf("%d %d %d %d => %d %d %d %d\n",rects[i].first.first,rects[i].first.second,rects[i].second.first,rects[i].second.second,x1,y1,x2,y2);
		#endif
		if(x1>x2)swap(x1,x2);
		if(y1>y2)swap(y1,y2);
		//このようにすると、和分したときに矩形が現れる
		paper_map[x1][y1]++;
		paper_map[x1][y2]--;
		paper_map[x2][y1]--;
		paper_map[x2][y2]++;
	}
	//外壁の追加。(0,0,width,height)から(1,1,width-1,height-1)を引き算する形。
	paper_map[0][0]++;
	paper_map[0][height]--;
	paper_map[width][0]--;
	paper_map[width][height]++;
	paper_map[1][1]--;
	paper_map[1][height-1]++;
	paper_map[width-1][1]++;
	paper_map[width-1][height-1]--;
	
	#ifdef DEBUG_PRINT
	for(int y=0;y<height+1;y++) {
		for(int x=0;x<width+1;x++) {
			printf("%2d ",paper_map[x][y]);
		}
		printf("\n");
	}
	#endif /* DEBUG_PRINT */
	
	//x方向に和分。
	for(int x=0;x<width+1;x++) {
		for(int y=0;y<height+1;y++) {
			if(x>0) paper_map[x][y]+=paper_map[x-1][y];
		}
	}
	//y方向に和分。
	for(int x=0;x<width+1;x++) {
		for(int y=0;y<height+1;y++) {
			if(y>0) paper_map[x][y]+=paper_map[x][y-1];
		}
	}
	
	#ifdef DEBUG_PRINT
	printf("\n");
	for(int y=0;y<height;y++) {
		for(int x=0;x<width;x++) {
			printf("%2d ",paper_map[x][y]);
		}
		printf("\n");
	}
	#endif /* DEBUG_PRINT */
	
	//ここでようやく領域の数を数える。
	int area_count=0;
	for(int x=1;x<width-1;x++) {
		for(int y=1;y<height-1;y++) {
			if(!paper_map[x][y]) {
				area_count++;
				//幅優先探索
				queue<pair<int,int> > que;
				que.push(make_pair(x,y));
				while(!que.empty()) {
					int cx=que.front().first;
					int cy=que.front().second;
					que.pop();
					if(!paper_map[cx][cy]) {
						paper_map[cx][cy]++;
						que.push(make_pair(cx-1,cy));
						que.push(make_pair(cx+1,cy));
						que.push(make_pair(cx,cy-1));
						que.push(make_pair(cx,cy+1));
					}
				}
			}
		}
	}
	
	#ifdef DEBUG_PRINT
	printf("\n");
	for(int y=0;y<height;y++) {
		for(int x=0;x<width;x++) {
			printf("%2d ",paper_map[x][y]);
		}
		printf("\n");
	}
	#endif /* DEBUG_PRINT */
	
	//出力して終了
	fprintf(out,"%d\n",area_count);
	
	fclose(out);
	fclose(in);
	return 0;
}