问题描述

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏,游戏在一个大小为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。

样例输入

3 3
0 2 0
1 1 1
2 0 2

样例输出

41255214

样例说明

行进路径如图1所示。

评测用例规模与约定

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

DFS

按方向顺序进行dfs，用四维数组存储经过的路径来判断是否交叉。
要注意数组的xy相较数轴的xy是旋转过的。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int n, k;
int m[N][N];
// 访问过的点和经过的路线
bool vis[N][N], check[N][N][N][N];
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

bool dfs(int x, int y, int step, string path)
{
    // 到达终点
    if (x == n - 1 && y == n - 1 && step == n * n - 1)
    {
        cout << path;
        return true;
    }
    for (int i = 0; i < 8; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        // 已经访问过
        if (vis[nx][ny])
            continue;
        // 超出边界
        if (nx < 0 || nx >= n || ny < 0 || ny >= n)
            continue;
        // 交叉
        if (check[nx][y][x][ny] || check[x][ny][nx][y])
            continue;
        // 数字不连续
        if ((m[nx][ny] != (m[x][y] + 1) % k))
            continue;
        // 行进并标记路线
        vis[nx][ny] = true;
        check[x][y][nx][ny] = true;
        // 递归搜索，如果找到路径则返回
        if (dfs(nx, ny, step + 1, path + to_string(i)))
            return true;
        // 回溯
        vis[nx][ny] = false;
        check[x][y][nx][ny] = false;
    }
    return false;
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> m[i][j];
    // 初始点已被访问
    vis[0][0] = true;
    if (!dfs(0, 0, 0, ""))
        cout << "-1";
    system("pause");
    return 0;
}