AOJ0548 Reindeer with no sense of direction

問題リンク Reindeer with no sense of direction

• 解法

プレゼントの置き順をそのまま追おうとすると４方向＋その中のどこに置くかで遷移先が多いですが、置いたプレゼントを逆に辿ろうとすると、最初にぶつかったプレゼントを取るしか選択肢がないので探索空間が小さくなる、というのがミソのようです（ギブアップして公式見ました）。
故に、辿っていないプレゼントの状態S、今いる位置Vの組み合わせについてDPもといメモ化探索すれば速く解けます。ですがまだAOJで通すことはできないです。メモリ制限に引っ掛かるからです。プレゼントの状態は2^23、位置は24通りあるので状態が億単位になるのです。ですが、実際存在しうるSとVの組み合わせはそれよりずっと小さいのでMapなどで存在しうる状態に対してのみ値を保持します。が、これでもメモリが足りません。そこで、プレゼントの残り数がある程度多い場合はまだ状態数が爆発していない部分なのでメモ化することなく逐一計算するようにしました。具体的には、８個目以降のプレゼントを回収したときに限りメモ化しています。これでようやく通りました。

• ソース

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

//Reindeer with no sense of direction
public class AOJ0548 {

	int w, h, N, GS, R = 8;
	int[][] map;
	int[][] d = {{-1,0},{0,1},{1,0},{0,-1}};
	List<Integer>[][] adj;
	Map<Integer, Integer>[] dp;
	
	int get(int v, int S, int rest){
		if(rest==1&&S==(1<<N))return 1;
		if(R<=rest&&dp[v].containsKey(S))return dp[v].get(S);
		int res = 0;
		for(int k=0;k<4;k++)for(int nv:adj[v][k]){
			if(((S>>nv)&1)==0)continue;
			if(nv==N&&3<=rest)continue;
			res+=get(nv, S-(1<<v), rest-1);
			break;
		}
		if(R<=rest)dp[v].put(S, res);
		return res;
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			w = sc.nextInt(); h = sc.nextInt();
			if((w|h)==0)break;
			N = 0;
			map = new int[h][w];
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				map[i][j] = sc.nextInt();
				if(map[i][j]==1)N++;
				else if(map[i][j]==0)map[i][j]=-1;
			}
			int id = 0;
			for(int i=0;i<h;i++)for(int j=0;j<w;j++){
				if(map[i][j]==-1)continue;
				if(map[i][j]==1){
					map[i][j]=id++;
				}
				else {
					map[i][j] = N;
				}
			}
			adj = new List[N+1][4];
			for(int i=0;i<=N;i++)for(int j=0;j<4;j++)adj[i][j]=new ArrayList<Integer>();
			for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(map[i][j]!=-1){
				for(int k=0;k<4;k++){
					int pi = i+d[k][0], pj = j+d[k][1];
					while(0<=pi&&pi<h&&0<=pj&&pj<w){
						if(map[pi][pj]!=-1)adj[map[i][j]][k].add(map[pi][pj]);
						pi+=d[k][0]; pj+=d[k][1];
					}
				}
			}
			GS = (1<<(N+1))-1;
			dp = new Map[N+1];
			for(int i=0;i<=N;i++)dp[i]=new HashMap<Integer, Integer>();
			dp[N].put(1<<N, 1);
			int res = 0;
			for(int k=0;k<4;k++)if(!adj[N][k].isEmpty())res+=get(adj[N][k].get(0), GS, N+1);
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ0548().run();
	}
}