练65.2 跳房子

解题思路

从25个格子各作为起点DFS，走五步形成六位串，每步只选四邻域合法位置，允许回到已走格子。把结果放入set去重。

正确性说明

依题目给出的对应关系逐项处理，位置与原输入保持明确对应。每一步完成当前项的全部贡献，结束后得到所有位置或字符的目标结果。

易错点

前导零是串的一部分，不限制格子重复访问；路径不同但六位串相同只算一次。

复杂度

最多25×4^5条路径，set操作另乘结果数量对数；空间为不同六位串数量。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a[5][5];
    for (auto &r : a)
        for (int &x : r)
            cin >> x;
    set<string> result;
    function<void(int, int, string)> dfs = [&](int x, int y, string s) {
        s += char('0' + a[x][y]);
        if (s.size() == 6) {
            result.insert(s);
            return;
        }
        int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
        for (int d = 0; d < 4; d++) {
            int i = x + dx[d], j = y + dy[d];
            if (i >= 0 && i < 5 && j >= 0 && j < 5)
                dfs(i, j, s);
        }
    };
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            dfs(i, j, "");
    cout << result.size() << "\n";
    return 0;
}