AOJ 0531 Paint Color

  • 概要

日本語の問題なので省略させて頂きます。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0531


  • 解法

幅 w (1 ≤ w ≤ 1000000 となる整数) と高さ h (1 ≤ h ≤ 1000000 となる整数)

とあるので当然普通にやったら要素数が足りません。

座標圧縮 をします。

座標圧縮については蟻本やJOIの解説を見るとわかりやすいです。

圧縮したあとはBFSで各座標について調べることで少ないオーダーで済ませることができます。

座標圧縮についてスライド作ろうとか思ったけど

より詳しい人に突っ込まれたくないのでやめておく(誰かお願いします

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#define MAX_N 1000

using namespace std;
typedef pair<int,int> P;
int n;
bool f[2*MAX_N+6][2*MAX_N+6];

int cp(int *z1,int *z2,int k)
{
	vector<int> xs;
	for(int i=0;i<n;i++){
		xs.push_back(z1[i]);
		if(z1[i]-1>=0)xs.push_back(z1[i]-1);
		xs.push_back(z2[i]-1);
		if(z2[i]<k)xs.push_back(z2[i]);
	}
	sort(xs.begin(),xs.end());
	xs.erase(unique(xs.begin(),xs.end()),xs.end());

	for(int i=0;i<n;i++){
		z1[i]=find(xs.begin(),xs.end(),z1[i])-xs.begin();
		z2[i]=find(xs.begin(),xs.end(),z2[i])-xs.begin();
	}

	return xs.size();
}

int main()
{
	int dx[4]={0,1,0,-1};
	int dy[4]={1,0,-1,0};
	int w,h;
	while(scanf("%d%d",&w,&h),w||h){
		scanf("%d",&n);
		int x1[MAX_N+1],x2[MAX_N+1],y1[MAX_N+1],y2[MAX_N+1];
		for(int i=0;i<n;i++){
			scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
		}

		w=cp(x1,x2,w);
		h=cp(y1,y2,h);

		memset(f,0,sizeof(f));
		for(int i=0;i<n;i++){
			for(int x=x1[i];x<x2[i];x++){
				for(int y=y1[i];y<y2[i];y++){
					f[x][y]=true;
				}
			}
		}

		int ans=0;
		for(int i=0;i<w;i++){
			for(int j=0;j<h;j++){
				if(f[i][j])continue;
				ans++;

				queue<P> q;
				q.push(make_pair(i,j));
				f[i][j]=true;
				while(!q.empty()){
					int x=q.front().first,y=q.front().second;
					q.pop();

					for(int l=0;l<4;l++){
						int xx=x+dx[l],yy=y+dy[l];
						if(xx<0 || xx>=w || yy<0 || yy>=h)continue;
						if(!f[xx][yy]){
							q.push(make_pair(xx,yy));
							f[xx][yy]=true;
						}
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

JOI本選進出者が発表されました。

自分もいますので、探してください。

http://www.ioi-jp.org/joi/2012/2013-yo-A-rank.html