AOJ0548 Reindeer with no sense of direction(方向音痴のトナカイ)

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0548
マス目状に表される町がある。
サンタは協会から出発し、全ての家にプレゼントを届け、協会に戻ってきたい。
しかし、方向音痴なトナカイは目的の家(or 協会)に降りるまで一直線に進むことしか出来ない。
更に、一度プレゼントを配った家には降りることが出来ない。
このようなとき、サンタがプレゼントを配る経路は何通りか。

解法

後ろから探索すると状態数が少なくなるという、なんか不思議な問題です。
プレゼントを配っていく問題ですが、後ろから探索するので、家に降りる度に奪っていきまだ奪っていない家の上は通れないという問題として考えます。
なんてひどいサンタ。

素直に前からやると、次に降りる家を決めるときに1つの方向でもしばしば候補が複数存在します。
しかし後ろからやると、まだプレゼントを奪っていない家よりも奥の家には行くことが出来なくなるので、1つの方向につきたかだか1つの家しか候補に上がりません。

メモ化配列(or DP配列)をmapにするだけではAOJだとMLEで通らなかったので、回った家の数が16以下の状態だけメモ化するという一般的なテクをやりました。
ちなみに、mapの計算量と探索の計算量の関係で、全部メモ化するより16以下だけメモ化したほうが速くなりました。

コード

using namespace std;
 
typedef long long ll;
 
const int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
const int MAX = 17;
int W, H, fld[10][10];
int P, sx, sy;
map<pair<pair<int, int>, int>, int> memo;
 
inline int CountBit(int s)
{
    int res = 0;
    for (int i = 0; i < P; i++) res += (s >> i) & 1;
    return res;
}
 
inline bool IsInside(int x, int y)
{
    return 0 <= x && x < W && 0 <= y && y < H;
}
 
inline bool CanDown(int x, int y, int s, int noBits)
{
    if (x == sx && y == sy && noBits == P) return true;
    if (fld[y][x] == -1) return false;
    return ((s >> fld[y][x]) & 1) == 0;
}
 
int DFS(int x, int y, int s)
{
    int cnt = CountBit(s);
    if (x == sx && y == sy && cnt == P) return 1;
    pair<pair<int, int>, int> state = make_pair(make_pair(x, y), s);
    if (cnt < MAX)
    {
        map<pair<pair<int, int>, int>, int>::iterator itr = memo.find(state);
        if (itr != memo.end()) return itr->second;
    }
    int sum = 0;
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        while (IsInside(nx, ny) && !CanDown(nx, ny, s, cnt))
            nx += dx[i], ny += dy[i];
        if (!IsInside(nx, ny)) continue;
        sum += DFS(nx, ny, s | (1 << fld[ny][nx]));
    }
    if (cnt < MAX) memo[state] = sum;
    return sum;
}
 
signed main()
{
    while (cin >> W >> H, W || H)
    {
        memo.clear();
        P = 0;
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                cin >> fld[i][j];
                if (fld[i][j] == 0) fld[i][j] = -1;
                else if (fld[i][j] == 1) fld[i][j] = P++;
                else sx = j, sy = i, fld[i][j] = -1;
            }
        }
        printf("%d\n", DFS(sx, sy, 0));
    }
    return 0;
}