1208 The Blocks Problem

問題概要

0番からn-1番のブロックがそれぞれ0番からn-1番のスペースに並んでいる。
これに対して次のような操作を行う。

move a onto b
aおよびbの上に積んであるブロックを全て初期位置の山に戻し、aをbの上に積む。
move a over b
aの上に積んであるブロックを全て初期位置の山に戻し、aをbの山の一番上に積む。
pile a onto b
bの上に積んであるブロックを全て初期位置の山に戻し、aの山をbの山の上に元の順のまま積む。
pile a over b
aの山のうち、aとそれよりも上の部分をbの山の一番上に元の順のまま積む。
quit
終了して山の状態を出力する。

ただし、aとbの数字が同じとき、またはaとbが同じ山に積まれているときはコマンドを無視するものとする。

解法

定義にしたがって実装する。山に相当するスタックをn個作ってシミュレート。
nは小さいので、各種操作はナイーブに実装してよい。

ソースコード

int n,p[25][25],m[25];
char s[10],t[10]; int a,b;

int find(int k)
{
	rep(i,n)rep(j,m[i])if(p[i][j]==k)return i;
	return inf;
}
int main()
{
	scanf("%d",&n);
	rep(i,n)m[i]=1,p[i][0]=i;
	
	while(scanf("%s",s),s[0]!='q')
	{
		scanf("%d%s%d",&a,t,&b);
		int pa=find(a),pb=find(b);
		if(a==b||pa==pb)continue;
		
		if(s[0]=='m'&&t[1]=='n')
		{
			for(int i=m[pa]-1;i>=0;i--)
			{
				if(p[pa][i]==a)break;
				int t=p[pa][i]; p[t][m[t]++]=t;
				m[pa]--;
			}
			for(int i=m[pb]-1;i>=0;i--)
			{
				if(p[pb][i]==b)break;
				int t=p[pb][i]; p[t][m[t]++]=t;
				m[pb]--;
			}
			p[pb][m[pb]++]=p[pa][--m[pa]];
		}
		else if(s[0]=='m'&&t[1]=='v')
		{
			for(int i=m[pa]-1;i>=0;i--)
			{
				if(p[pa][i]==a)break;
				int t=p[pa][i]; p[t][m[t]++]=t;
				m[pa]--;
			}
			p[pb][m[pb]++]=p[pa][--m[pa]];
		}
		if(s[0]=='p'&&t[1]=='n')
		{
			for(int i=m[pb]-1;i>=0;i--)
			{
				if(p[pb][i]==b)break;
				int t=p[pb][i]; p[t][m[t]++]=t;
				m[pb]--;
			}
			rep(i,m[pa])p[pb][m[pb]++]=p[pa][i];
			m[pa]=0;
		}
		else if(s[0]=='p'&&t[1]=='v')
		{
			int na; for(na=0;na<m[pa];na++)if(p[pa][na]==a)break;
			
			rep(i,m[pa]-na)p[pb][m[pb]++]=p[pa][i+na];
			m[pa]=na;
		}
	}
	rep(i,n)
	{
		printf("%d:",i);
		rep(j,m[i])printf(" %d",p[i][j]); puts("");
	}
	
	return 0;
}