「AOJ531～540」の編集履歴（バックアップ）一覧に戻る

AOJ531～540 - (2011/11/04 (金) 11:04:59) の編集履歴(バックアップ)

---

---

0531　Paint Color

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531
ベニヤ板をマスキングテープで区切り、区切られた部分を全て違う色でぬるとき何色必要か。
マスキングテープの頂点情報とベニヤ板のサイズからそれを答えよという問題です。

解法
Y軸と平行に1単位ごとにベニヤ板を区切り、隣の列と同じテープの張られ方をしている列を全てまとめてベニヤ板を圧縮します。
後は列ごとに隣の列と比較しテープの貼られてない領域をコネクトしていき、コネクトされてできた森の数を数えれば答えが出ます。
下記コードは上記の考え方に基づき記述したものです。
実行速度で正答者40位中3位をとったコードですが、コードサイズが膨らんでしまいました。
おそらくもっとシンプルな考え方で色数を計算できるはずですので他の方のコードを参考にしてください。

#include<stdio.h>
#include<vector>
#include<set>
#include <algorithm>
struct point{
int x1,x2,y,inOut;
bool operator<(const point p)const{
	if(y!=p.y)return y<p.y;
	return inOut>p.inOut;
}
void set(int xi,int xi2,int yi,int inOuti){
	x1=xi;
	x2=xi2;
	y=yi;
	inOut=inOuti;
}
};
std::vector<bool> moveOKs;
void connectSearch(std::vector<std::set<int> >& con,int now){
std::set<int>::iterator it=con[now].begin();
moveOKs[now]=false;
while(it!=con[now].end()){
	if(moveOKs[(*it)]==true)connectSearch(con,(*it));
	it++;
}
}
void setData(int w,int h){
int n;
point p;
scanf("%d",&n);
int x1,y1,x2,y2;
std::vector<point> points;
std::set<int> xs;
moveOKs.clear();	
for(int i=0;i<n;i++){
	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	p.set(x1,x2,y1,1);
	points.push_back(p);
	p.set(x1,x2,y2,-1);
	points.push_back(p);
	xs.insert(x1);
	xs.insert(x2);
}
xs.insert(0);
p.set(0,w,0,1);
points.push_back(p);
p.set(0,w,0,-1);
points.push_back(p);
p.set(0,w,h,1);
points.push_back(p);	
std::sort(points.begin(),points.end());
std::set<int>::iterator it=xs.begin();
int nowX,colorCount=0,size;
int inOutCount,now,old,turn=0;
std::vector<int> yMemo[2];
std::vector<int> yNoMemo[2];
std::vector<std::set<int> > connect;
std::set<int> dammySet;	
while(it!=xs.end()){
	nowX=(*it);
	inOutCount=0;
	now=turn%2;
	old=(turn+1)%2;
	turn++;
	yMemo[now].clear();
	yNoMemo[now].clear();
	size=points.size()-1;
	for(int i=0;i<size;i++){
		if(nowX<points[i].x1 || points[i].x2<=nowX)continue;
		//printf("(%d %d %d %d %d) \n",i,points[i].x1,points[i].x2,points[i].y,points[i].inOut);
		inOutCount+=points[i].inOut;
		if(inOutCount==0){
			yMemo[now].push_back(points[i  ].y);
			int tempy=points[i].y;
			while(tempy==points[i].y || nowX<points[i].x1 || points[i].x2<=nowX){
				i++;
				if(points[i].x1<=nowX && nowX<points[i].x2){
						inOutCount+=points[i].inOut; 
						//printf("(%d %d %d %d %d) \n",i,points[i].x1,points[i].x2,points[i].y,points[i].inOut);
				}
			}
			yMemo[now].push_back(points[i].y);
			yNoMemo[now].push_back(-1);
		}
	}
	//printf("\n%d\n",yMemo[now].size());
	if(yMemo[now].empty()){
		it++;
		continue;
	}
	/*
	for(int i=0;i<yMemo[now].size();i+=2){
		printf("(%d %d)",yMemo[now][i],yMemo[now][i+1]);
	}
	printf("\n");
	*/
	size=yMemo[now].size();
	unsigned int oldP=0,nowP=0;
	int y1,y2,y3,y4;
	while(oldP<yMemo[old].size() && nowP<yMemo[now].size()){
		y1=yMemo[old][oldP  ];
		y2=yMemo[old][oldP+1];
		y3=yMemo[now][nowP  ];
		y4=yMemo[now][nowP+1];
		if(y2<=y3){
			oldP+=2;
		}else if(y1>=y4){
			if(yNoMemo[now][nowP/2]==-1){
				yNoMemo[now][nowP/2]=colorCount;
				connect.push_back(dammySet);
				colorCount++;
				moveOKs.push_back(true);
			}
			nowP+=2;
		}else{
			if(yNoMemo[now][nowP/2]==-1){
				yNoMemo[now][nowP/2]=yNoMemo[old][oldP/2];
			}else{
				connect[yNoMemo[now][nowP/2]].insert(yNoMemo[old][oldP/2]);
				connect[yNoMemo[old][oldP/2]].insert(yNoMemo[now][nowP/2]);
			}
			if(y2>y4){
				nowP+=2;
			}else if(y2<y4){
				oldP+=2;
			}else{
				nowP+=2;
				oldP+=2;
			}
		}
	}
	for(unsigned int i=nowP;i<yMemo[now].size();i+=2){
		if(yNoMemo[now][i/2]==-1){
			yNoMemo[now][i/2]=colorCount;
			connect.push_back(dammySet);
			colorCount++;
			moveOKs.push_back(true);
		}
	}
	it++;
}
int sum=0;
for(unsigned int i=0;i<moveOKs.size();i++){
	if(moveOKs[i]==true){
		sum++;
		connectSearch(connect,i);
	}
}
printf("%d\n",sum);
}
int main(){
int w,h;
while(1){
	scanf("%d %d",&w,&h);
	if(w==0 && h==0) break;
	setData(w,h);
}
}