PKU演習問メモ(10/25)

PKU
No. 問題名 問題の種類および解法 難易度
1166 The Clocks 幅優先探索 ★★☆☆☆

1166 The Clocks

問題概要

状態が0→1→2→3→0→……と変わるダイアルが9つあり、それぞれの名前をABCDEFGHIとする。
これらについて、

  • ABDE
  • ABC
  • BCEF
  • ADG
  • BDEFH
  • CFI
  • DEGH
  • GHI
  • EFHI

の9通りのうちいずれかの組のダイアルを同時に1回だけ回す操作ができる。
全てのダイアルを0にするための手順のうち最小回数のものを一つ出力せよ。

解法

ダイアルの取りうる状態数は4^9=330万。
よって訪問済みノードを覚えておく幅優先探索で十分間に合う。


ダイアルの状態を4進数と見て、一つの整数にするのが自然。

ソースコード

なんかセンスのないコードになってしまった。

char *g[]={"ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};
int gain[9][9];
int move[330000];

int toi(int *a)
{
	int n=0;
	rep(i,9)n<<=2,n+=a[i];
	return n;
}
void toa(int *a,int n)
{
	rep(i,9)a[8-i]=n&3,n>>=2;
}

int main()
{
	rep(i,9)for(int j=0;g[i][j];j++)gain[i][g[i][j]-'A']=1;
	
	int st[9]={0};
	rep(i,9)scanf("%d",st+i);
	int si=toi(st);
	
	rep(i,330000)move[i]=-1;
	queue<int> Q; Q.push(si);
	while(!Q.empty())
	{
		int s=Q.front(); Q.pop();
		if(s==0)break;
		rep(i,9)
		{
			int a[9]; toa(a,s); rep(j,9)a[j]=a[j]+gain[i][j]&3;
			int nx=toi(a);
			if(move[nx]>=0)continue;
			move[nx]=i; Q.push(nx);
		}
	}
	
	vi ans;
	for(int p=0;p!=si;)
	{
		ans.pb(move[p]);
		int a[9]; toa(a,p); rep(i,9)a[i]=a[i]+4-gain[move[p]][i]&3;
		p=toi(a);
	}
	int n=ans.size();
	rep(i,n)
	{
		if(i)putchar(' ');
		printf("%d",ans[n-i-1]+1);
	}
	puts("");
	
	return 0;
}