AOJ1268 Cubic Eight-Puzzle - nanikakaのAOJ航海日誌

概要

図3のようなサイコロと、3*3のグリッドがある。グリッドの初期状態は図4のような形であり、空マスとなる座標は入力で与えられる。1ステップにつき、サイコロを1つだけ空マスへ転がすことができる。入力で与えられる目標状態(グリッドを上から見下ろした時に見える色)にするために必要な最小ステップ数を答えよ。最小ステップ数が30を超える場合は-1と答えよ。

解法

幅優先探索だと状態数が爆発するので、反復深化法で解きました。
サイコロは普通24通りの状態を取りますが、この問題では、上面の色と前面の色の2つさえ決まればサイコロの状態が決定できるので6通りの状態しかありません。よって、サイコロは0〜5の数字で表せます。
あるグリッドの状態において、整数difを[目標状態と色が違うマスの数]とします。すると、このグリッドが目標状態へ到達するためには最低でもdif-1回のステップが必要となります。よって、現在の探索の深さとdif-1の和が、深さの制限を超えるようならば刈ることができます。difが0のときは即ち目標状態に到達したことを表します。
この枝刈りの工夫だけだとまだ時間がかかりすぎるのでもう1つ。直前のステップの状態に戻るような転がし方をしない、という制約をつけるだけで結構早くなります。サイコロを右に転がしたら次のステップでそのサイコロを左に転がさない、ということです。

ソース

import java.util.Scanner;

//Cubic Eight-Puzzle
public class AOJ1268 {

	int[] top = {0, 0, 1, 1, 2, 2, 3};
	int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
	int[][] adj = {
			{2, 5, 2, 5},
			{4, 3, 4, 3},
			{0, 4, 0, 4},
			{5, 1, 5, 1},
			{1, 2, 1, 2},
			{3, 0, 3, 0}
	};

	int[][] goal, state;
	boolean dfs(int ei, int ej, int depth, int limit, int pre){
		int dif = 0;
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)dif+=top[state[i][j]]!=goal[i][j]?1:0;
		if(dif==0)return true;
		if(limit<depth+dif-1)return false;
		for(int k=0;k<4;k++){
			if(pre==(k+2)%4)continue;
			int ni = ei+d[k][0], nj = ej+d[k][1];
			if(0<=ni&&ni<3&&0<=nj&&nj<3){
				state[ei][ej] = adj[state[ni][nj]][k]; state[ni][nj] = 6;
				if(dfs(ni, nj, depth+1, limit, k))return true;
				state[ni][nj] = adj[state[ei][ej]][k]; state[ei][ej] = 6;
			}
		}
		return false;
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int x = sc.nextInt(), y = sc.nextInt();
			if((x|y)==0)break;
			goal = new int[3][3];
			for(int i=0;i<3;i++)for(int j=0;j<3;j++){
				char c = sc.next().charAt(0);
				goal[i][j] = c=='W'?0:c=='R'?1:c=='B'?2:3;
			}
			state = new int[3][3];
			state[y-1][x-1] = 6;
			int res = -1;
			for(int L=0;L<=30;L++){
				if(dfs(y-1, x-1, 0, L, -1)){
					res = L; break;
				}
			}
			System.out.println(res);
		}
	}

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