JAG春コンテスト 2011年度(2012?) 問題 C Billiards Sorting (AOJ 2391)

問題

1番から順に番号のついたビリヤードの球が、下図のようにn段に並んでいる。

        [ 5]
      [ 2][ 3]
    [ 4][ 1][ 6]
  [ 7][ 8][ 9][10]
[11][12][13][14][15]

1の球に対して、上下に隣接する球のいずれかと入れ替える操作を行うことができる。

        [ 1]
      [ 2][ 3]
    [ 4][ 5][ 6]
  [ 7][ 8][ 9][10]
[11][12][13][14][15]

の状態にするまでに必要な操作の回数の最小値を求めよ。
ただし、与えられる状態は、45手以内に解を持つことが保証されている。

制約条件

n≦5

解法

頑張って探索する。
マンハッタン距離(的なもの)の総和をコストの推定値とするようなA*を書いたらMLEだった。


両側探索が効率的っぽい。
23手分ゴールから最初に探索してハッシュに入れておく。

ソースコード

void solve_small(vi);

const int dy[] = {-1, -1, 1, 1}, dx[] = {-1, 0, 0, 1};
map<ll, int> M;
int n, num[5][5];

inline ll hash(const vi &v){
	ll res = 0;
	rep(i,v.size()) res *= 17, res += v[i];
	return res;
}
inline void push(const vi &v, int c, queue<pair<int,vi> > &q){
	ll h = hash(v);
	if(M.count(h))return;
	M[h] = c;
	if(c <= 22) q.push(make_pair(c+1, v));
}

int main(){
	
	queue<pair<int,vi> > q;
	vi goal;
	int k = 0;
	rep(i,5) rep(j,i+1){
		num[i][j] = k;
		goal.push_back(++k);
	}
	push(goal, 0, q);
	
	while(!q.empty()){
		vi v = q.front().second;
		int c = q.front().first; q.pop();
		
		int idx = -1, y, x;
		for(y = 0; y < 5; y++) for(x = 0; x <= y; x++)
			if(v[++idx] == 1) goto OUT;
		OUT:;
		rep(d,4){
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= 5 || nx > ny) continue;
			swap(v[num[ny][nx]], v[idx]);
			push(v, c, q);
			swap(v[num[ny][nx]], v[idx]);
		}
	}
	int cs = 0;
	
	while(cin >> n, n){
		
		cout << "Case " << ++cs << ": ";
		
		vi v(n*(n+1)/2);
		k = 0;
		rep(i,n) rep(j,i+1) cin >> v[k++];
		if(n <= 4){
			solve_small(v);
			continue;
		}
		
		ll h = hash(v);
		if(M.count(h)){
			cout << M[h] << endl;
			continue;
		}
		
		queue<pair<int,vi> > q;
		set<ll> s;
		s.insert(h);
		q.push(make_pair(0, v));
		while(!q.empty()){
			v = q.front().second;
			int c = q.front().first; q.pop();
			
			int idx = -1, y, x;
			for(y = 0; y < 5; y++) for(x = 0; x <= y; x++)
				if(v[++idx] == 1) goto OUT2;
			OUT2:;
			rep(d,4){
				int ny = y + dy[d], nx = x + dx[d];
				if(ny < 0 || nx < 0 || ny >= 5 || nx > ny) continue;
				swap(v[num[ny][nx]], v[idx]);
				ll h = hash(v);
				if(M.count(h)){
					cout << M[h] + c + 1 << endl;
					goto END;
				}
				if(!s.count(h)) q.push(make_pair(c+1, v)), s.insert(h);
				swap(v[num[ny][nx]], v[idx]);
			}
		}
		END:;
	}
	return 0;
}

void solve_small(vi v){
	vi goal = v;
	sort(goal.begin(), goal.end());
	queue<pair<int,vi> > q;
	set<ll> s;
	ll ghash = hash(goal);
	q.push(make_pair(0, v));
	
	while(!q.empty()){
		v = q.front().second;
		int c = q.front().first; q.pop();
		ll h = hash(v);
		if(s.count(h)) continue;
		s.insert(h);
		if(h == ghash){
			cout << c <<endl; return;
		}
		int idx = -1, y, x;
		for(y = 0; y < 5; y++) for(x = 0; x <= y; x++)
			if(v[++idx] == 1) goto OUT3;
		OUT3:;
		rep(d,4){
			int ny = y + dy[d], nx = x + dx[d];
			if(ny < 0 || nx < 0 || ny >= n || nx > ny) continue;
			swap(v[num[ny][nx]], v[idx]);
			if(!s.count(hash(v))) q.push(make_pair(c+1, v));
			swap(v[num[ny][nx]], v[idx]);
		}
	}
}