2010 ICPC国内予選 D.ぐらぐら

ICPC 実装問題

問題概要

テトリスのようにピースを積み重ねてオブジェを作るとき、そのオブジェが安定かどうかを判定せよ。


ただしオブジェが安定であるとは、全てのピースに対して、
そのピースおよびそのピースが支える全てのピースをあわせた重心が、そのピースと、それを支えるピースの接する部分のうち、最も左のx座標から最も右のx座標の間に含まれることをいう。（境界は含まない）

  • 最も下のピースは地面に接している。
  • ピースとピースは面がぴったりくっついている。
  • ピースは樹状に積み重ねられている。

ことを仮定してよい。

解法

ピース同士で、あるピースがあるピースを支えているという関係を有向グラフにする。
そして地面に接するピースから、深さ優先探索で「各ピースおよびそのピースが支える全てのピースをあわせた」重心の位置とピースのサイズを求める。
そして深さ優先探索で全てのピースが安定かどうかを判定すればよい。

ソースコード

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

int w,h;
char in[100][100];

bool e[1000][1000];
int mnx[1000],mxx[1000];
int id[100][100];
int npc,sz[1000];
double xsum[1000];

void nul(int y,int x,int num,char bl)
{
	xsum[num]+=x+0.5;
	sz[num]++;
	
	rep(d,4)
	{
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0&&nx<0||ny>=h||nx>=w||in[ny][nx]!=bl)continue;
		if(id[ny][nx]>=0)continue;
		id[ny][nx]=num; nul(ny,nx,num,bl);
	}
}
void getsize(int num)
{
	rep(i,npc)if(e[num][i])
	{
		getsize(i);
		sz[num]+=sz[i];
		xsum[num]+=xsum[i];
	}
}

bool stable(int num)
{
	rep(i,npc)if(e[num][i])
	if(!stable(i))return 0;
	if(xsum[num]/sz[num]<=mnx[num]||mxx[num]<=xsum[num]/sz[num])return 0;
	
	return 1;
}

int main()
{
	while(cin>>w>>h,w){
		rep(i,h)cin>>in[i];
		
		npc=0;
		rep(i,h)rep(j,w)id[i][j]=-1;
		
		rep(i,h)rep(j,w)if(id[i][j]<0&&in[i][j]!='.')
		{
			id[i][j]=npc;
			sz[npc]=xsum[npc]=0;
			nul(i,j,npc,in[i][j]); npc++;
		}
		
		rep(i,npc)
		{
			rep(j,npc)e[i][j]=0;
			mnx[i]=inf,mxx[i]=-inf;
		}
		rep(i,h-1)rep(j,w)if(id[i+1][j]!=id[i][j])
		{
			int d=id[i+1][j],u=id[i][j];
			if(d<0||u<0)continue;
			
			e[d][u]=1;
			mnx[u]=min(mnx[u],j);
			mxx[u]=max(mxx[u],j+1);
		}
		rep(i,w)if(id[h-1][i]>=0)
		{
			int d=id[h-1][i];
			mnx[d]=min(mnx[d],i);
			mxx[d]=max(mxx[d],i+1);
		}
		
		int root=0;
		for(;root<npc;root++)
		{
			rep(i,npc)if(e[i][root])goto NEXT;
			break; NEXT:;
		}
		getsize(root);
		cout<<(stable(root)?"STABLE":"UNSTABLE")<<endl;
	}
	return 0;
}