AOJ0548 - ド素人のメモ帳

■問題
教会と家の情報がn*mの盤面で与えられます。
トナカイは上下左右に直進しかできず、一度止まった家の上は通過できなくなります。
教会からスタートし、すべての家に訪れてまた教会に戻ってくるルートは何通りあるか求めよ。

■解法
まずこの問題の一番厄介なところは一度止まった家の上を通過できなくなるというところだが、それはゴールからスタートに向かうと考えると通った家は必ず止まる、同じ家に止まらないという事だけ考えれば良いことになる。
探索に必要な情報はどの家に止まったかと今の座標であり、今の座標は家に番号を振り分けておくと一つですみ、どの家に止まったかをbitで管理すると、dp[どの家に止まったかのbit][今いる家の番号]で答えを求めることができる。

この開放のオーダーを考えると家の数をhとするとO(2^h * h)となり、家の数は最大23であるため、つらそうに見えるが、どの家に止まったかのbitは盤面では実現不可能な状態も多くあり、計算量はもっと少なくなる。

答えとソースのみを送るJOI予選ならこれでいいのだが、オンラインジャッジだとメモリが足りなくてMLEになってしまうためいろいろ工夫しなくてはならない。
オーダーのとこで言ったように実現不可能な状態も配列で確保すると必要になり無駄なので、mapを使ってdpする。
これでも足りないが、訪れた家の数が多くなっていくにつれ、探索する量も減っていくため、探索の多い訪れた家の数が少ない(立っているbitが少ない)時のみメモし、小さい時は毎回探索することによりメモリを減らすことができる。
いくつになったら毎回探索に切り替えるかはメモリの上限と実行時間とか考えながら適当な値にする（これでは13とかにしてる）。

■ソース

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <string>
#define F first
#define S second
using namespace std;
int n,m;
int c;
int f[22][22];
typedef pair<int,int> P;
vector<P> v;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
bool used[33];
map<P,int> dp;
int solve(int bit,int h){
  if(bit == (1<<c)-1){
    if(v[h].F == v[0].F || v[h].S == v[0].S){
      return 1;
    }
    return 0;
  }

  if(dp.find(P(bit,h)) != dp.end()){
    return dp[P(bit,h)];
  }

  int ret = 0;
  for(int i = 0; i < 4; i++){
    int nx = v[h].F + dx[i];
    int ny = v[h].S + dy[i];
    while(0 < nx && nx <= n && 0 < ny && ny <= m){
      if(f[nx][ny] && !used[f[nx][ny]]){
	used[f[nx][ny]] = true;
	ret += solve(bit | (1<<f[nx][ny]),f[nx][ny]);
	used[f[nx][ny]] = false;
	break;
      }
      nx += dx[i];
      ny += dy[i];
    }
  }
  if(__builtin_popcount(bit) < 13) dp[P(bit,h)] = ret;
  return ret;
}

int main(void){
  while(1){
    cin >> n >> m; if(!n) break;
    c = 1;
    v.clear();
    v.push_back(P(0,0));
    memset(f,0,sizeof(f));
    memset(used,false,sizeof(used));
    for(int i = 1; i <= m; i++){
      for(int j = 1; j <= n; j++){
	cin >> f[j][i];
	if(f[j][i] == 2){
	  v[0].F = j;
	  v[0].S = i;
	  f[j][i] = 0;
	}else if(f[j][i] == 1){
	  f[j][i] = c;
	  v.push_back(P(j,i));
	  c++;
	}
      }
    }

    dp.clear();
    cout << solve(1,0) << endl;
  }
}