5989.数字接龙

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

游戏规则如下：

从左上角 (0,0) 处出发，目标是到达右下角 (N−1,N−1) 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。
对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：0,1,2,…,K−1,0,1,2,…,K−1,0,1,2…0,1,2,…,K−1,0,1,2,…,K−1,0,1,2…。
途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。
路径中不可以出现交叉的线路。例如之前有从 (0,0) 移动到 (1,1)，那么再从 (1,0) 移动到 (0,1) 线路就会交叉。

为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图 22 所示；因此行进路径可以用一个包含 0…70…7 之间的数字字符串表示，如下图 11 是一个迷宫示例，它所对应的答案就是：4125521441255214。

现在请你帮小蓝规划出一条行进路径并将其输出。

如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 −1。

输入格式

第一行包含两个整数 N,K

接下来输入 N 行，每行 N 个整数表示棋盘格子上的数字。

输出格式

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

数据范围

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

输入样例：

输出样例：

41255214

解析：

const int N = 11;
int g[N][N];
bool st[N][N], edge[N][N][N][N];
int n, k;
int dx[] = { -1,-1,0,1,1,1,0,-1 };
int dy[] = { 0,1,1,1,0,-1,-1,-1,0 };
string path;

N 是一个常量，表示网格的最大尺寸。
g 是一个二维数组，用于存储网格中每个点的值。
st 是一个二维数组，用于标记每个点是否已经被访问过。
edge 是一个四维数组，用于标记两个点之间是否存在边。
n 和 k 是输入的变量，分别表示网格的大小和一个用于判断路径合法性的模数。
dx 和 dy 是两个数组，用于表示八个方向的偏移量。
path 是一个字符串，用于存储找到的路径。

深度优先搜索函数 `dfs`：

bool dfs(int a, int b) {
    if (a == n - 1 && b == n - 1) {
        return path.size() == n * n - 1;
    }
    st[a][b] = true;
    for (int i = 0; i < 8; i++) {
        int x = a + dx[i];
        int y = b + dy[i];
        if (x < 0 || x >= n || y < 0 || y >= n) {
            continue;
        }
        if (st[x][y]) continue;
        if (g[x][y] != (g[a][b] + 1) % k) {
            continue;
        }
        if (i % 2 && edge[a][y][x][b] || edge[x][b][a][y]) {
            continue;
        }
        edge[a][b][x][y] = true;
        path += i + '0';
        if (dfs(x, y)) {
            return true;
        }
        path.pop_back();
        edge[a][b][x][y] = false;
    }
    st[a][b] = false;
    return false;
}

这个函数使用深度优先搜索算法来尝试找到一条从当前点 (a, b) 到右下角的合法路径。
如果当前点是右下角且路径长度等于网格中所有点的数量减一，则返回 true，表示找到了一条合法路径。
然后，它遍历八个方向，检查每个方向上的点是否合法（未超出边界、未被访问过、值满足条件、没有边冲突）。
如果某个方向上的点合法，则标记该点为已访问，将该方向添加到路径中，并递归调用 dfs 函数。
如果递归调用返回 true，则表示找到了一条合法路径，返回 true。
如果递归调用返回 false，则回溯，将该方向从路径中移除，并标记该点为未访问。
如果所有方向都尝试过但没有找到合法路径，则返回 false。

注意：在这段代码中，(g[a][b] + 1) % k 的目的是确保路径上的每个点的值满足一定的条件。具体来说，它要求路径上的每个点的值比前一个点的值大 1，并且在达到 k 时循环回到 0。

主函数 `main`：

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }
    if (!dfs(0, 0)) {
        cout << "-1";
    }
    cout << path;
    return 0;
}

主函数首先读取网格的大小 n 和模数 k。
然后，它读取网格中每个点的值，并将其存储在 g 数组中。
接着，它调用 dfs 函数从左上角开始搜索路径。
如果没有找到合法路径，则输出 -1。
最后，它输出找到的路径。
时间复杂度： $O(n^2)$
空间复杂度： $O(n^4)$

完整代码：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 11;
int g[N][N];
bool st[N][N],edge[N][N][N][N];
int n, k;
int dx[]={ -1,-1,0,1,1,1,0,-1 };
int dy[] = {0,1,1,1,0,-1,-1,-1,0};
string path;
bool dfs(int a, int b) {
	if (a == n - 1 && b == n - 1) {
		return path.size()==n*n-1;
	}
	st[a][b] = true;
	for (int i = 0; i < 8; i++) {
		int x = a + dx[i];
		int y = b + dy[i];
		if (x<0 || x>=n || y<0 || y>=n) {
			continue;
		}
		if(st[x][y]) continue;
		if (g[x][y] != (g[a][b] + 1)%k) {
			continue;
		}
		if (i%2 && edge[a][y][x][b] || edge[x][b][a][y]) {
			continue;
		}
		edge[a][b][x][y] = true;
		path+=i + '0';
		if (dfs(x, y)) {
			return true;
		}
		path.pop_back();
		edge[a][b][x][y] = false;
	}
	st[a][b] = false;
	return false;
}
int main() {
	cin>>n>>k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> g[i][j];
		}
	}
	if(!dfs(0,0)){
	    cout<<"-1";
	}
	cout<<path;
	return 0;
}