题目描述

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为N × N 的格子棋盘上展开，其中每一个格子处都有着一个 0 . . . K − 1 之间的整数。游戏规则如下：

1. 从左上角 (0, 0) 处出发，目标是到达右下角 (N − 1, N − 1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . . 。
3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。
4. 路径中不可以出现交叉的线路。例如之前有从 (0, 0) 移动到 (1, 1)，那么再从 (1, 0) 移动到 (0, 1) 线路就会交叉。
   为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2 所示；因此行进路径可以用一个包含 0 . . . 7 之间的数字字符串表示，如下图 1是一个迷宫示例，它所对应的答案就是：41255214。
   
   现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

输入格式

第一行包含两个整数 N、K。
接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。

输出格式

输出一行表示答案。如果存在答案输出路径，否则输出 −1。

样例输入1

3 3
0 2 0
1 1 1
2 0 2

样例输出1

41255214

样例说明

行进路径如图 1 所示。

评测用例规模与约定

对于 80% 的评测用例：1 ≤ N ≤ 5。
对于 100% 的评测用例：1 ≤ N ≤ 10，1 ≤ K ≤ 10。

血的教训。。耗费时间太多了，导致其它题都没怎么做。因为数据范围小，直接爆搜，不用考虑剪枝。

代码如下：

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

const int N = 20;

int g[N][N];
bool st[N][N];
int n, k;
vector<int> res;

typedef pair<int, int> PII;

int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}, dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};


void dfs(int x, int y, vector<int> v)
{
    // 选出字典序最小的
    if(x == n && y == n)
    {
        if(v.size() == n * n - 1)
        {
            if(res.size() == 0) res = v;
            else 
            {
                for(int i = 0; i < v.size(); i ++) 
                    if(v[i] < res[i])
                    {
                        res = v;
                        break;
                    }
                    else if(res[i] < v[i]) break;
            }
        }
        else return;
    }

    for(int i = 0; i < 8; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        // 这里我防止交叉的办法是 !st[a][y] || !st[x][b]，假如是一个2*2的矩阵
        // st[a][y]以及st[x][b]刚好是矩阵的另一条对角线，这样就能判断是否交叉了
        if((g[a][b] == (g[x][y] + 1) % k) && (!st[a][y] || !st[x][b]) && !st[a][b] && a >= 1 && a <= n && b >= 1 && b <= n)
        {
            v.push_back(i);
            st[a][b] = true;
            dfs(a, b, v);
            // 状态回溯
            v.pop_back();
            st[a][b] = false;
        }
    }

    return;
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &g[i][j]);

    // 左上角元素要特判0，好像比赛的时候没有注意到这个，G了
    if(g[1][1] != 0)
    {
        cout << -1 << endl;
        return 0;
    }
    vector<int> v;
    st[1][1] = true;
    dfs(1, 1, v);

    if(!res.size()) cout << -1 << endl; 
    else for(int i = 0; i <= res.size() - 1; i ++) cout << res[i];
    return 0;
}