AOJ 0531 Paint Color

AOJ

問題概要

幅w高さhのベニヤ板に、四頂点の座標がx1[i],y1[i],x2[i],y2[i]で与えられる長方形のテープをn枚貼る。
このとき、テープの貼られていないベニヤ板の部分がいくつの部分に分かれているかを求めよ。
w,hは1000000以下の整数、各頂点はベニヤ板の内部（周含む）の格子点である。

解法

ICPCなどで頻出の"島数え問題"のちょっと難しい版。難しいのは、

  • 塗りつぶしの範囲（島の大きさ）が最大400万なので再帰で書くとスタックオーバーフローする点
  • 座標圧縮が必要な点

である。

座標圧縮についての解説は日本語のものが皆無に等しいので、後でこのブログで解説記事を書こうと思う。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};

int w,h,n;
int x1[1000],x2[1000],y1[1000],y2[1000],X,Y;
bool v[2006][2006];
vi x,y;

int main()
{
	while(cin>>w>>h,w)
	{
		cin>>n;
		x.clear(); y.clear();
		
		rep(i,n)
		{
			cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
			x.pb(x1[i]),y.pb(y1[i]);
			x.pb(x2[i]),y.pb(y2[i]);
		}
		
		x.pb(0),y.pb(0); x.pb(w),y.pb(h);
		sort(all(x)); sort(all(y));
		x.erase(unique(all(x)),x.end()); y.erase(unique(all(y)),y.end());
		
		X=x.size(),Y=y.size();
		rep(i,n)
		{
			x1[i]=lower_bound(all(x),x1[i])-x.begin();
			y1[i]=lower_bound(all(y),y1[i])-y.begin();
			x2[i]=lower_bound(all(x),x2[i])-x.begin();
			y2[i]=lower_bound(all(y),y2[i])-y.begin();
		}
		
		rep(i,Y)rep(j,X)v[i][j]=i==Y-1||j==X-1;
		rep(i,n)for(int a=x1[i];a<x2[i];a++)
		for(int b=y1[i];b<y2[i];b++)v[b][a]=1;
		
		int ans=0;
		rep(i,Y)rep(j,X)if(!v[i][j])
		{
			ans++;
			v[i][j]=1;
			queue<pair<int,int> > Q; Q.push(make_pair(i,j));
			while(!Q.empty()){
				int a=Q.front().first,b=Q.front().second; Q.pop();
				rep(d,4)
				{
					int ny=a+dy[d],nx=b+dx[d];
					if(ny<0||nx<0||ny>=Y-1||nx>=X-1||v[ny][nx])continue;
					v[ny][nx]=1;
					Q.push(make_pair(ny,nx));
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

出典

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0531
Source: 第7回 日本情報オリンピック 2008年2月10日