2011/11/04(Fri) 09:12:08 編集(投稿者)
結局グラフで解く方法を思いつかず前回この板で質問したシートの周計を求める問題を応用して解きました。
列を比べた時同じ状態の列を無視し隣の列とエリアを結合して数え上げる方法をとりました。
コードが膨らむのは思考力やプログラマとしての実力が低いからです。
コード実行速度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);
}
}