AOJ2137 Time Trial

問題リンク Time Trial

• 概要

W*Hのマップがある。
マップには岩とパネルが3つずつあり、全ての岩をパネルの上に運びたい。
人は1ステップにつき、上下左右に動ける。進んだ先に岩があった場合、その先が壁や別の岩でなければ押すことができる。
このパズルを攻略する最短ステップ数を答えよ。
以下のことが保証されている。
パズルは必ず解ける
壁でないマスの数は高々50
岩とパネルは必ず3つずつある
マップの周囲は必ず壁である
4 <= W, H <= 16

• 解法

マスが高々50しかないので、岩の状態は 50C3 = 19600 通りしかありません。これに加えて人物の状態も50通りまでしかないので、結局、パズルの状態は19600 * 50 = 980000 < 10^6 通りしかないことになります。よって幅優先探索で解くことができます。
パズルの状態をうまくコーディングできるかがカギになると思います。

• ソース

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

//Time Trial
public class AOJ2137 {

	void run(){
		Scanner sc = new Scanner(System.in);
		int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
		//岩の状態(i, j, k)に0〜19599の番号を振る ※(i < j < k)
		int[][][] assign = new int[50][50][50];
		//岩の状態の番号から、岩の位置を復元する表
		int[][] ref = new int[19600][3];
		int ID = 0;
		for(int i=0;i<50;i++)for(int j=i+1;j<50;j++)for(int k=j+1;k<50;k++){
			ref[ID][0] = i; ref[ID][1] = j; ref[ID][2] = k;
			assign[i][j][k]=ID++;
		}
		boolean[][] u = new boolean[19600][50];
		for(;;){
			int w = sc.nextInt(), h = sc.nextInt();
			if((w|h)==0)break;
			char[][] map = new char[h][];
			//id[i][j]: (i, j)マスにつけた番号
			//番号 A のマスの座標 = (rid[A][0], rid[A][1])
			int[][] id = new int[h][w], rid = new int[50][2];
			int[] tile = new int[3], rock = new int[3];
			int kt = 0, kr = 0, start = 0, M = 0;
			for(int i=0;i<h;i++){
				map[i] = sc.next().toCharArray();
				for(int j=0;j<w;j++){
					if(map[i][j]=='@'){
						id[i][j] = M;
						rid[M][0] = i; rid[M][1] = j;
						start = M++;
					}
					else if(map[i][j]=='_'){
						id[i][j] = M;
						rid[M][0] = i; rid[M][1] = j;
						tile[kt++] = M++;
					}
					else if(map[i][j]=='*'){
						id[i][j] = M;
						rid[M][0] = i; rid[M][1] = j;
						rock[kr++] = M++;
					}
					else if(map[i][j]=='.'){
						rid[M][0] = i; rid[M][1] = j;
						id[i][j] = M++;
					}
					else id[i][j] = -1;
				}
			}
			int G = assign[tile[0]][tile[1]][tile[2]], S = assign[rock[0]][rock[1]][rock[2]];
			for(boolean[]a:u)Arrays.fill(a, false);
			u[S][start] = true;
			List<int[]> l = new ArrayList<int[]>();
			l.add(new int[]{S, start});
			int step = 0, res = -1;
			while(!l.isEmpty()){
				List<int[]> next = new ArrayList<int[]>();
				for(int[] a:l){
					if(G==a[0]){
						res = step; next.clear(); break;
					}
					int[] r = ref[a[0]], nr = new int[3];
					int pi = rid[a[1]][0], pj = rid[a[1]][1];
					for(int k=0;k<4;k++){
						int ni = pi+d[k][0], nj = pj+d[k][1], npos = id[ni][nj];
						if(npos==-1)continue;
						nr[0] = r[0]; nr[1] = r[1]; nr[2] = r[2];
						int mpos = id[ni+d[k][0]][nj+d[k][1]];
						if(r[0]==npos){
							if(mpos==-1||r[1]==mpos||r[2]==mpos)continue;
							nr[0] = mpos;
						}
						else if(r[1]==npos){
							if(mpos==-1||r[0]==mpos||r[2]==mpos)continue;
							nr[1] = mpos;
						}
						else if(r[2]==npos){
							if(mpos==-1||r[0]==mpos||r[1]==mpos)continue;
							nr[2] = mpos;
						}
						Arrays.sort(nr);
						int ns = assign[nr[0]][nr[1]][nr[2]];
						if(!u[ns][npos]){
							u[ns][npos] = true; next.add(new int[]{ns, npos});
						}
					}
				}
				step++;
				l = next;
			}
			System.out.println(res);
		}
	}

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