AOJ Problem 0548 : Reindeer with no sense of direction

404 Not Found

まあ、分からないからJOIの解説見ちゃうよね。逆から見るって発想は無かった。

にしても、解法分かったところでAOJのメモリ制約がキツいのは変わらないので、強引な改善をしながら解きました。

• とりあえず辿った家の数が19(適当な定数)未満ならメモ化する。

これでやっと通った。

#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

#define END (64)
#define EMPTY (-2)
#define WALL (-1)

int px[24],py[24],kx,ky;
int H,W,N;
int field[12][12];

int dx[] = {0,-1,0,1} , dy[] = {1,0,-1,0};

map<int,int> memo[24];

int dfs(int pos , int bit , bool done[12][12]){
	if(memo[pos].find(bit) != memo[pos].end() ) return memo[pos][bit];
	
	
	// 全部の家に辿った後教会に帰れるかどうか
	if(bit == (1<<N)-1){
		rep(d,4){
			int cx = px[pos]+dx[d] , cy = py[pos]+dy[d];
			while( field[cy][cx] != WALL){
				if(field[cy][cx] == END) return 1;
				cy += dy[d] , cx += dx[d];
			}
		}
		return 0;
	}
	
	// それ以外なら辿ってない家で最初に到着する家を見つける。
	int ans = 0;
	rep(d,4){
		int cx = px[pos]+dx[d] , cy = py[pos]+dy[d];
		while( field[cy][cx] == EMPTY || field[cy][cx] == END || done[cy][cx] == true ){
			cy += dy[d] , cx += dx[d];
		}
		if(field[cy][cx] != WALL){
			done[cy][cx] = 1;
			ans += dfs(field[cy][cx] , bit | (1<<field[cy][cx]) , done);
			done[cy][cx] = 0;
		}
	}
	
	// 辿った家の数が19未満ならメモる。(メモリ対策)
	if(__builtin_popcount(bit) < 19)
		memo[pos][bit] = ans;
	return ans;
}

int main(){
	while(cin >> W >> H ,W){
		// 初期化
		N = 0;
		rep(i,12)rep(j,12)field[i][j] = WALL;
		
		// 入力
		rep(i,H)rep(j,W){
			int t;
			cin >> t;
			switch(t){
			case 0:
				field[i+1][j+1] = EMPTY;
				break;
			case 1:
				field[i+1][j+1] = N;
				px[N] = j+1, py[N] = i+1;
				N++;
				break;
			case 2:
				kx = j+1 , ky = i+1;
				field[i+1][j+1] = END;
				break;
			}
		}
		px[N] = kx , py[N] = ky;
		
		// 探索
		rep(i,24) memo[i].clear();
		bool done[12][12]={{false}};
		cout << dfs(N,0,done) << endl;
	}
}