AOJ1245 Gap

問題リンク Gap

• 概要

Gapというカードゲームをやる。これをクリアするまでにかかる最短の手数を答えよ。
Gapは4*8のボードを使い、1〜4の柄それぞれについて1〜7の数が1枚ずつある。ボードには常に4か所の空欄がある。
1手につき、空欄にカードを移動することができる。移動させられるカードは、その空欄の左隣りのカードと柄一緒で数が1だけ大きいカードだけである。つまり、空欄の左隣りも空欄であったり、左隣りのカードの数が7だったりすると、その空欄にカードを移動させられない。
Gapの初期状態が与えられる。初期状態から、数が1であるカードを左の列に移動させたところからゲームが始まる。この移動は手数のカウントに含まない。
クリアできる手順が無い場合は-1と答えよ。

• 解法

方針はメモ化再帰です。
カード1枚は2文字の文字列で表せます(空欄は"00"としました）。これを32個並べて長さ64の文字列でゲームの状態を表すことにします。Mapにはキーがマップの状態で、値はその状態に至る最短ステップです。
再帰の各ステップでは空欄の場所を探します。空欄の場所に来ることができるカードが無いならばそこは無視します。あれば、そのカードを移動させるために、ボードの中から探します。ここの処理を少し速くするために、大きさ48の配列に、各カードがボードのどこにあるかを覚えておくようにしました(カード15はpos[15]に入っているand so on.）。
例によって例のごとく、メモリが足りるか不安でしたが何とかなりました。

• ソース

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//Gap
public class AOJ1245 {

	String trans(){
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<4;i++)for(int j=0;j<8;j++){
			sb.append(a[i][j]==0?"00":a[i][j]);
		}
		return sb.toString();
	}
	
	int min, INF = 1<<29;
	int[][] a;
	int[] pos;
	String g = "1112131415161700212223242526270031323334353637004142434445464700";
	Map<String, Integer> ref;
	
	void dfs(int d){
		String r = trans();
		if(min<=d||ref.containsKey(r)&&ref.get(r)<=d)return;
		if(r.equals(g)){
			min = d;return;
		}
		ref.put(r, d);
		for(int i=0;i<4;i++)for(int j=1;j<8;j++){
			if(a[i][j]!=0||a[i][j-1]==0||a[i][j-1]%10==7)continue;
			int x = a[i][j-1]+1;
			int p = pos[x];
			a[p/8][p%8] = 0; a[i][j] = x;
			pos[x] = i*8+j;
			dfs(d+1);
			a[p/8][p%8] = x; a[i][j] = 0;
			pos[x] = p;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while(T--!=0){
			min = INF;
			a = new int[4][8];
			for(int i=0;i<4;i++)for(int j=1;j<8;j++){
				a[i][j]=sc.nextInt();
			}
			for(int i=0;i<4;i++)for(int j=1;j<8;j++){
				if(a[i][j]%10==1){
					int t = a[i][j]/10-1;
					a[t][0] = a[i][j];
					a[i][j] = 0;
				}
			}
			pos = new int[48];
			for(int i=0;i<4;i++)for(int j=0;j<8;j++){
				if(a[i][j]==0)continue;
				pos[a[i][j]] = i*8+j;
			}
			ref = new HashMap<String, Integer>();
			dfs(0);
			System.out.println(min==INF?-1:min);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1245().run();
	}
}