POJ 1175 Starry Night

問題

'0','1'のHxWマスのグリッドで表される星空がある。
'1'のマスが上下左右斜めにつながっている部分は一つの星座とみなす。


それぞれの星座にアルファベットの小文字を割り当てて出力せよ。
ただし、回転、反転をさせると重なる星座には同じ文字を割り当てよ。

制約条件

W,H≦100
星座の数≦500

方針

素直に全ての星座をvector<string>として表し、mapに入れるなどして全列挙する。
回転や反転をして、vector<string>として最小になるものをmapに入れるようにした。


ここの実装は愚直にやって間に合った。

ソースコード

int w,h;
char in[100][101];
bool tmp[100][100];

int mnx,mxx,mny,mxy;

void nul(int y,int x,char c=0){
	char prev=in[y][x];
	
	if(c)in[y][x]=c;
	else{
		tmp[y][x]=1;
		mnx=min(mnx,x); mxx=max(mxx,x);
		mny=min(mny,y); mxy=max(mxy,y);
	}
	
	for(int ny=y-1;ny<y+2;ny++)for(int nx=x-1;nx<x+2;nx++)
	if(0<=ny&&ny<h&&0<=nx&&nx<w)if(ny!=y||nx!=x){
		if(c&&in[ny][nx]==prev)nul(ny,nx,c);
		if(!c&&!tmp[ny][nx]&&in[ny][nx]==in[y][x])nul(ny,nx);
	}
}
void rot(vector<string> &cluster){
	vector<string> res(cluster[0].size(),string(cluster.size(),'0'));
	rep(i,cluster.size())rep(j,cluster[0].size())
	res[j][cluster.size()-1-i]=cluster[i][j];
	cluster=res;
}
void mirror(vector<string> &cluster){
	rep(i,cluster.size())
	rep(j,cluster[0].size()/2)swap(cluster[i][j],cluster[i][cluster[0].size()-1-j]);
}

int main()
{
	scanf("%d%d",&w,&h);
	rep(i,h)scanf("%s",in+i);
	
	int k=0;
	map<vector<string>,int> m;
	
	rep(i,h)rep(j,w)if(in[i][j]=='1'){
		memset(tmp,0,sizeof(tmp));
		mnx=mxx=j; mny=mxy=i;
		nul(i,j);
		
		vector<string> cluster(mxy-mny+1,string(mxx-mnx+1,'0')), regular;
		
		rep(y,mxy-mny+1)rep(x,mxx-mnx+1)if(tmp[y+mny][x+mnx]){
			cluster[y][x]='1';
		}
		
		rep(it,8){
			if(regular.empty() || regular > cluster)regular = cluster;
			rot(cluster);
			if(it==3)mirror(cluster);
		}
		
		if(!m.count(regular))m[regular]=k++;
		nul(i,j,'a'+m[regular]);
	}
	
	rep(i,h)puts(in[i]);
	
	return 0;
}