2158-Double Sorting

問題概要

数字二つのペアがn個ある．隣り合ったペアの2つの数値を交換することが出来るとき，ペアがソートされた状態になるのは最小何回の交換が必要か．

解法

最良優先探索+嘘枝刈り．
各数値の正しい位置との距離が近い順に探索する．
さらに，後ろからBFSをある程度して計算する量を大幅に減らすようにする．
がこれだけでは通らず，さらに謎な定数調整が必要になってしまった．

実装(C++)

#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tr1/unordered_map>
using namespace std;
typedef unsigned long long ull;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
int n;
int p[2][8];
ull pow_eight[16]={ 1ULL, 8ULL, 64ULL, 512ULL, 4096ULL, 32768ULL, 262144ULL, 2097152ULL, 16777216ULL, 134217728ULL, 1073741824ULL, 8589934592ULL, 68719476736ULL, 549755813888ULL, 4398046511104ULL, 35184372088832ULL};
ull mul[16][8];
int res[8]={0,2,5,10,15,23,31,40};
struct State{
	ull hash;
	int value[8][2];
	int dist;
	void init(){
		hash=0;
		REP(i,n){
			REP(j,2){
				value[i][j]=p[j][i];
				dist+=abs(i-value[i][j]);
			}
			if(value[i][0]>value[i][1])swap(value[i][0],value[i][1]);
		}
		REP(i,n)REP(j,2)hash+=mul[i*2+j][value[i][j]];
	}
	void swap_value(int k,int a,int b){
		REP(i,2){
			REP(j,2){
				dist-=abs(i+k-value[i+k][j]);
				hash-=mul[(i+k)*2+j][value[i+k][j]];
			}
		}
		swap(value[k][a],value[k+1][b]);
		REP(i,2){
			if(value[i+k][0]>value[i+k][1]){
				swap(value[i+k][0],value[i+k][1]);
			}
		}
		REP(i,2){
			REP(j,2){
				dist+=abs(i+k-value[i+k][j]);
				hash+=mul[(i+k)*2+j][value[i+k][j]];
			}
		}

	}
	State(){
		hash=0;
		dist=0;
	}
};
bool operator<(const State &a,const State &b){
	return a.dist>b.dist;
}
tr1::unordered_map<ull,int> bfs[9];
tr1::unordered_map<ull,int> ac;
int solve(){
	priority_queue<State> que;
	State s;
	ac.clear();
	s.init();
	que.push(s);
	ac[s.hash]=0;
	int ans=34;
	while(!que.empty()){
		State tmp=que.top();que.pop();
		int now=ac[tmp.hash];
		int nn=tmp.dist;
		if(now>=ans)continue;
		if((tmp.dist+1)/2+now>=ans)continue;
		if(bfs[n].find(tmp.hash)!=bfs[n].end()){
			ans=min(ans,now+bfs[n][tmp.hash]);
			continue;
		}
		State next;
		for(int i=0;i<n-1;i++){
			REP(a,2)REP(b,2){
				next=tmp;
				next.swap_value(i,a,b);
				if(next.dist<=nn){
					if(ac.find(next.hash)==ac.end()||ac[next.hash]>now+1){
						ac[next.hash]=now+1;
						que.push(next);
					}
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}
void BFS(){
	queue<State> que;
	State s;
	ac.clear();
	s.init();
	que.push(s);
	ac[s.hash]=0;
	while(!que.empty()){
		State tmp=que.front();que.pop();
		int now=ac[tmp.hash];
		bfs[n][tmp.hash]=now;
		if(now>=5)return;
		State next;
		for(int i=0;i<n-1;i++){
			REP(a,2)REP(b,2){
				next=tmp;
				next.swap_value(i,a,b);
				if(ac.find(next.hash)==ac.end()){
					ac[next.hash]=now+1;
					que.push(next);
				}
			}
		}
	}
}
int main(){
	REP(i,8)REP(j,16)mul[j][i]=i*pow_eight[j];
	for(n=1;n<=8;n++){
		REP(i,n)REP(j,2){
			p[j][i]=i;
		}
		BFS();
	}
	while(cin>>n,n){
		REP(i,n){
			REP(j,2){
				cin>>p[j][i];
				p[j][i]--;
			}
		}
		bool ps=true;
		REP(i,n){
			if(!(p[0][i]==n-i-1&&p[1][i]==n-i-1)){
				ps=false;break;
			}
		}
		if(ps){
			cout<<res[n-1]<<endl;continue;
		}
		solve();
	}
	return 0;
}