2040-Sort the Panels

AOJ

問題概要

探検者は古代のビルに辿りついたが，入口には鍵がかかっていた．
入口にはいくつかの黒または白のパネルが一直線上の等間隔で置いてある．
鍵を開けるにはパネルの順番を正しいものにしなくてはならない．

さて，鍵をあけるにはパネルの順番を変更する特殊な機械を使わなくてはならない．
この機械に出来ることは二つのパネルを交換することだけだ．その交換は次のように行なわれる．
1. 機械を一つのパネルの前に動かしマークする
2．機械をもう一つのパネルの前に動かしマークする
3．特殊なボタンを押すと機械は二つのマークされたパネルを交換する．

3つ以上のパネルをマークすることは出来ず，パネルを交換した時点でマークはリセットされる．

探検者はパネルの順番を正しい順番にしようとしたが，機械が重すぎて，出来るだけ少ない回数の移動で済ましたいと思った．

あなたはパネルを正しい順番にするときの最小の移動回数を求めるプログラムを書け．ただしマシンの初期位置はどこに設定しても良い．

解法

目標のパネルと現在のパネルの差が大きくなる方向には探索しないようにすると，DAGになるので動的計画法を用いることが出来る．
後は現在のパネルの状態(2^16)と現在の機械の位置(16)でメモ化再帰探索をする．
計算量は2^16*16*16*16だが，全ての状態を取るわけでは無いので間に合う．

実装(C++)

#include <algorithm>
#include <iostream>
using namespace std;

#define REP(i,x) for(int i=0;i<(int)(x);i++)

inline int check(int a,int b,int n){//aとbの一致度のチェック
	int ans=0;
	for(int i=0;i<n;i++){
		if(((a>>i)&1)==((b>>i)&1)){
			ans++;
		}
	}
	return ans;
}
int string2int(const string &a){
	int res=0;
	REP(i,a.size()){
		if(a[i]=='B')res|=1<<i;
	}
	return res;
}
int swap(int a,int b,int target){
	int mask=(~(1<<a))&(~(1<<b));
	mask&=target;
	if((target>>a)&1)mask|=1<<b;
	if((target>>b)&1)mask|=1<<a;
	return mask;
}
int dp[1<<16][16];
int solve(int a,int now,int target,int n){
	int k=check(a,target,n);
	if(k==n)return 0;
	int &res=dp[a][now];
	if(res==-1){
		res=999999;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(i==j)continue;
				int next=swap(i,j,a);
				if(check(next,target,n)>k){
					res=min(res,solve(next,j,target,n)+abs(i-now)+abs(j-i));
				}
			}
		}
	}
	return res;
}
int main(){
	int n;
	for(;cin>>n,n;){
		string in[2];
		cin>>in[0]>>in[1];
		int ans=9999999;
		REP(i,1<<n)REP(j,n)dp[i][j]=-1;
		REP(i,n){
			ans=min(ans,solve(string2int(in[0]),i,string2int(in[1]),n));
		}
		cout<<ans<<endl;
	}
	return 0;
}