AOJ2040 Sort the Panels - nanikakaのAOJ航海日誌

概要

N個の'W'と'B'からなるパネルの順列S, Tが与えられる。次のルールに従ってSをTへ変化させるのにかかるコストを最小化せよ。
機械が1台ある。機械は任意のパネルへ移動してマークをつける。続けてもう1か所別のパネルへ移動してマークをつけ、マークをつけた箇所のパネルをスワップする。コストは機械が移動した距離である。また、機械の初期位置は任意に選ぶことができる。機械を初期配置に置くことにコストはかからない。
SからTの順列を得る手順が必ず存在することが保証されている。
2 <= N <= 16

解法

(パネルの状態、機械の位置)をノードとしたダイクストラで解きます。パネルの状態はB, Wを0, 1と思えば1つの整数値で表すことができます。
(s, p)からの次のノードは1個目のマークをつける箇所a, 2個目のマークをつける箇所bを選び、sのaビット目とbビット目をスワップした状態ns、位置bです。移動コストはpからaへ、aからbへ動く距離の和なので、d[s][p]+abs(p-a)+abs(a-b)です。
スワップする個所a, bは、揃っている箇所を崩すと絶対損になるだろうと予想して、sのaビット目とbビット目がTのaビット目とbビット目と両方とも異なっている場合のみ、スワップを行うということにしています。この予想はどうやら当たりだったようです。

ソース

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

//Sort the Panels
public class AOJ2040 {

	int[][] dist;
	int n, M = 20, INF = 1<<29, S, G;
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			char[] t1 = sc.next().toCharArray(), t2 = sc.next().toCharArray();
			S = 0; G = 0;
			for(int i=0;i<n;i++){
				S+=t1[i]=='W'?1<<i:0; G+=t2[i]=='W'?1<<i:0;
			}
			dist = new int[1<<n][n];
			for(int[]a:dist)Arrays.fill(a, INF);
			PriorityQueue<Integer> q = new PriorityQueue<Integer>(n, new Comparator<Integer>() {
				public int compare(Integer o1, Integer o2) {
					return dist[o1/M][o1%M]-dist[o2/M][o2%M];
				}
			});
			for(int i=0;i<n;i++){
				dist[S][i] = 0; q.add(S*M+i);
			}
			while(!q.isEmpty()){
				int V = q.poll();
				int s = V/M, p = V%M;
				if(s==G){
					System.out.println(dist[s][p]); break;
				}
				for(int a=0;a<n;a++){
					int pa = s&(1<<a);
					if(pa==(G&(1<<a)))continue;
					for(int b=0;b<n;b++){
						if(a==b||(s&(1<<b))==(G&(1<<b)))continue;
						int w = dist[s][p]+Math.abs(p-a)+Math.abs(a-b);
						int pb = s&(1<<b), ns = s;
						if(pa>0)ns|=1<<b;
						else ns&=~(1<<b);
						if(pb>0)ns|=1<<a;
						else ns&=~(1<<a);
						if(w<dist[ns][b]){
							dist[ns][b] = w; q.add(ns*M+b);
						}
					}
				}
			}
		}
	}

	public static void main(String[] args) {
		new AOJ2040().run();
	}
}