BFS计算邻接矩阵，DFS+回溯暴力搜索，可以状态caching进一步优化，状态定义：[源节点][长度为node数的01字符串表示结点的访问状态]，但是，重叠子问题比较少，只能做到常数级别的优化，相应的，状态空间庞大，呈阶乘级别增长

LintCode_1693.小财迷走迷宫.cpp

/*   题目描述：
给定一个 n * m 的迷宫 maze, 其中:
. 表示空地
S 表示起点
T 表示终点
* 表示障碍物
0~9 表示不同的宝物
请问从起点开始, 在拿到所有宝物之后走到终点, 最少需要多少步? 如果无法拿到全部的宝物并走到终点, 返回 -1.
样例
样例 1:
输入：["T1S.",".*0*","....","..*."]
输出：4
解释：(0,2)->(1,2)->(0,2)->(0,1)->(0,0)
样例 2:
输入：["1*S.","..0.","T..."]
输出：6
解释：(0,2)->(1,2)->(1,1)->(1,0)->(0,0)->(1,0)->(2,0)
注意事项
n, m <= 50
迷宫中的数字是连续的, 并且从 0 开始. 每个数字最多出现一次.
地图上除了障碍物以外的所有点都可以行走.
在收集完所有宝物之前, 终点可以被当做空地.
*/

// O((k + 2)*m*n + k!): k为宝物数量

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#include <cassert>

using namespace std;

    inline int pack(int x, int y) {
        return ((x << 8) | y);
    }

    bool bfs(vector<vector<int> >& dists, unordered_map<int, int>& mp,
             vector<vector<bool> >& visited, const vector<string>& maze,
             int m, int n, int Sx, int Sy) {
        for (int i = 0; i != m; ++i) fill(visited[i].begin(), visited[i].end(), false);
        queue<pair<int, int> > q;
        q.push({Sx, Sy});
        int SKey = mp[pack(Sx, Sy)];
        // check valid and calc dists
        int cnt = 0, step = 0;
        while (!q.empty()) {
            int s = q.size();
            while (s--) {
                auto C = q.front(); q.pop();
                int x = C.first, y = C.second;
                if (x == -1 || y == -1 || x == m || y == n) continue;
                if (maze[x][y] == '*') continue;
                if (visited[x][y]) continue;
                visited[x][y] = true;
                int key = pack(x, y);
                if (mp.count(key)) {
                    int TKey = mp[key];
                    dists[SKey][TKey] = step;
                    if (++cnt == dists.size()) break;
                }
                q.push({x - 1, y});
                q.push({x + 1, y});
                q.push({x, y - 1});
                q.push({x, y + 1});
            }
            ++step;
        }
        return cnt == dists.size();
    }

    int minSteps(const vector<vector<int> >& dists, vector<bool>& reached, int remain, int SKey, int TKey) {
        if (SKey == TKey) {
            assert(dists[SKey][TKey] == -1);
            return remain == 0 ? 0 : INT_MAX;
        }
        int minStep = INT_MAX;
        reached[SKey] = true;
        for (int i = 0; i != dists[SKey].size(); ++i) {
            if (reached[i]) continue;
            int subStep = minSteps(dists, reached, remain - 1, i, TKey);
            if (subStep == INT_MAX) continue;
            minStep = min(minStep, dists[SKey][i] + subStep);
        }
        reached[SKey] = false;
        return minStep;
    }

    int minSteps(vector<string>& maze) {
        // Write your code here
        int m = maze.size(), n = maze[0].size();
        int Sx, Sy, Tx, Ty, cnt = 0;
        unordered_map<int, int> mp;
        vector<pair<int, int> > digits;
        for (int i = 0; i != m; ++i) {
            for (int j = 0; j != n; ++j) {
                if (isdigit(maze[i][j])) mp[pack(i, j)] = cnt++;
                else if (maze[i][j] == 'S') { Sx = i; Sy = j; mp[pack(i, j)] = cnt++; }
                else if (maze[i][j] == 'T') { Tx = i; Ty = j; mp[pack(i, j)] = cnt++; }
            }
        }
        vector<vector<int> > dists(cnt, vector<int>(cnt, -1));
        vector<vector<bool> > visited(m, vector<bool>(n));
        if (!bfs(dists, mp, visited, maze, m, n, Sx, Sy)) return -1;
        for (const auto& item : mp) {
            int x = (item.first >> 8), y = (item.first & ((1 << 8) - 1));
            if (maze[x][y] == 'S' || maze[x][y] == 'T') continue;
            bfs(dists, mp, visited, maze, m, n, x, y);
        }
        vector<bool> reached(cnt, false);
        return minSteps(dists, reached, cnt - 1, mp[pack(Sx, Sy)], mp[pack(Tx, Ty)]);
    }

int main() {
/*
    vector<string> maze =
{"T1S.",
 ".*0*",
 "....",
 "..*."};    // ans: 4
    vector<string> maze =
{"1*S.",
 "..0.",
 "T..."};           // ans: 6
*/

    vector<string> maze =         // ans: 130
{"..................................................",
 "........*......*..............*..................*",
 "....*.............................................",
 "....................*......................*......",
 "................................*.*...............",
 "..................................................",
 "..........*.......................................",
 "...........*......................................",
 "..................................................",
 "...................*..............................",
 "...................*..............................",
 "...........1......................................",
 ".....*.....................................*......",
 "...............S..................................",
 "...............................*........*.........",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..*...............................................",
 "..................................................",
 "..................................................",
 "..................................................",
 ".............*...*.................*..............",
 ".....................*......................*.....",
 ".*....................................*...........",
 ".................*................................",
 "..................*...............................",
 "..................................................",
 "...............*.......*..........................",
 "..................................................",
 "....................................*.............",
 "..*..................*............................",
 "..........*..................0....................",
 ".4*....................................2..........",
 "..........................*.......................",
 "..................................................",
 "..................................................",
 "..................................................",
 "........................................*.........",
 ".......*..........................................",
 "..................................................",
 "..................................................",
 "..................................................",
 "..................................................",
 ".*...................................*............",
 "................T............................3...."};
    cout << minSteps(maze) << endl;
    return 0;
}