AOJ 0548: Reindeer with no sense of direction

まず、逆向き(プレゼントを拾う方向)に考えると探索空間が減ることが、この問題の重要な性質です。これに気が付かないとAOJでは通せないと思います。

AOJの場合、実行時間制限とメモリ制限が厳しく、ナイーブな探索やDPでは解けないので、少し工夫する必要があります。
DPで解く場合はmapを使い、使わなくなったメモリを解放すればMLEしないで済みます。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
typedef pair<int,int> P;


int g[10][10],m,n,dx[]={1,0,-1,0},dy[]={0,1,0,-1},px[24],py[24];


int main(){
	while(scanf("%d%d",&m,&n),m){
		map<P,int> dp;
		int h = 1,ans = 0;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				scanf("%d",g[i]+j);
				if(g[i][j]==2){
					g[i][j]=-1;
					px[0] = i;
					py[0] = j;
				}else if(g[i][j]){
					g[i][j] = h;
					px[h] = i;
					py[h] = j;
					h++;
				}
			}
		}
		dp[make_pair(0,(1<<h-1)-1)] = 1;
		
		for(int i = 0; i < h; i++){
			map<P,int> nextdp;
			for(map<P,int>::iterator it = dp.begin(); it != dp.end(); ++it){
				P p = (*it).first;
				int use = p.second;
				for(int j = 0; j < 4; j++){
					int x = px[p.first];
					int y = py[p.first];
					while(0<=x && x<n && 0<=y && y<m){
						if(use&(1<<g[x][y]-1)){
							int use2 = use ^ (1<<g[x][y]-1);
							nextdp[make_pair(g[x][y],use2)] += dp[make_pair(p.first,use)];
							break;
						}else if(!use && g[x][y]==-1){
							ans += dp[make_pair(p.first,use)];
							break;
						}
						x += dx[j];
						y += dy[j];
					}
				}
			}
			dp = nextdp;
		}
		printf("%d\n",ans);
	}
	
	return 0;
}