题目描述

在一个 $N \times N$ 的棋盘上，每个格子 $(i, j)$ (0-indexed) 有一个整数 $g_{i,j}$，其值在 $0$ 到 $K-1$ 之间。我们需要找到一条从左上角 $(0, 0)$ 到右下角 $(N-1, N-1)$ 的路径，满足以下所有条件：

1. 移动: 每一步可以从当前格子移动到相邻的 8 个方向（水平、垂直、对角线）之一的格子。
2. 数字序列: 路径经过的格子上的数字序列必须是 $0, 1, 2, \dots, K-1, 0, 1, 2, \dots, K-1, 0, \dots$ 的形式。也就是说，如果当前格子的数字是 $v$，下一个格子的数字必须是 $(v+1) \pmod K$。
3. 访问: 棋盘上的每个格子必须恰好经过一次。这意味着路径的长度必须是 $N^2$ 个格子（$N^2-1$ 步移动）。
4. 非交叉: 路径不能自交叉。例如，如果路径包含了 $(0,0) \to (1,1)$ 的移动，那么它就不能再包含 $(1,0) \to (0,1)$ 的移动。
5. 目标: 最终必须到达右下角 $(N-1, N-1)$。
6. 路径表示: 路径用一个由方向编号（0到7）组成的字符串表示，如下图所示：
   7 0 1 6 X 2 5 4 3
   其中 X 是当前格子。例如，向右移动是方向 2，向右下移动是方向 3。

如果存在满足条件的路径，输出字典序最小的那条路径字符串。如果不存在，输出 -1。

样例

输入:
3 3
0 2 0
1 1 1
2 0 2

输出:
41255214

说明:
路径对应的格子序列为: (0,0) -> (1,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) -> (1,1) -> (2,0)。
格子上的数字序列为: 0 -> 1 -> 2 -> 0 -> 1 -> 2 -> 0 -> 1 -> 2。
方向序列为: 4 (下) -> 1 (右上) -> 2 (右) -> 5 (左下) -> 5 (左下) -> 2 (右) -> 1 (右上) -> 4 (下)。
最终到达 (2,2) 即 (N-1, N-1)。所有格子恰好访问一次。

算法 (深度优先搜索 DFS + 回溯)

时间复杂度 $O(\text{指数级别})$

思路分析

这是一个典型的在网格图上寻找满足特定条件的路径的问题，并且要求访问所有节点恰好一次（哈密尔顿路径问题的一种变体）。由于 $N$ 的范围较小（最大为 10），我们可以考虑使用深度优先搜索 (DFS) 结合回溯来暴力搜索所有可能的路径。同时，我们需要满足数字序列约束和非交叉约束，并且找到字典序最小的路径。

1. DFS 状态:
   我们的 DFS 函数需要知道当前所在的格子位置 (a, b)。还需要记录已经访问过的格子、当前构建的路径字符串以及路径中已经包含的边（用于非交叉检查）。

2. DFS 过程:

   • 基本框架:
     dfs(a, b) 函数尝试从格子 (a, b) 出发，继续寻找满足条件的路径。
   • 标记: 进入 dfs(a, b) 时，将格子 (a, b) 标记为已访问。
   • 基础情况 (Base Case):
     如果当前格子 (a, b) 是目标格子 $(N-1, N-1)$：
     检查当前路径是否访问了所有的 $N \times N$ 个格子。可以通过比较当前路径字符串 path 的长度是否等于 $N^2 - 1$ 来判断。如果是，说明找到了一条完整的有效路径，返回 true。
   • 递归探索 (Recursive Step):
     按照字典序的要求，我们需要按方向 0 到 7 的顺序尝试移动到下一个格子。
     对于每个方向 i (从 0 到 7)：
     1. 计算下一个格子的坐标 (x, y) = (a + dx[i], b + dy[i])。
     2. 检查移动的合法性:
        • 边界检查: (x, y) 是否在 $N \times N$ 的棋盘内？
        • 访问检查: (x, y) 是否已经被访问过？（使用 st 数组）
        • 数字序列检查: 下一个格子的数字 g[x][y] 是否等于 (g[a][b] + 1) % k？
        • 非交叉检查:
          • 这个检查只对对角线移动 (i 为奇数，即 1, 3, 5, 7）是必要的。
          • 当从 (a, b) 移动到 (x, y) 时，这条线段可能会与连接 (a, y) 和 (x, b) 的线段交叉。
          • 我们需要检查路径中是否已经存在从 (a, y) 到 (x, b) 的移动，或者从 (x, b) 到 (a, y) 的移动。
          • 使用一个 4 维布尔数组 edge[r1][c1][r2][c2] 来记录路径中是否存在从 (r1, c1) 到 (r2, c2) 的移动。
          • 因此，在进行对角线移动 i 之前，检查 edge[a][y][x][b] 和 edge[x][b][a][y] 是否都为 false。
     3. 递归调用: 如果移动合法：
        • 记录这次移动：将 edge[a][b][x][y] 设为 true。
        • 将方向 i 对应的字符添加到路径字符串 path 中。
        • 递归调用 dfs(x, y)。
        • 处理结果: 如果递归调用返回 true，说明找到了完整路径，直接返回 true。
     4. 回溯 (Backtracking): 如果递归调用返回 false，或者移动不合法，说明从当前方向 i 出发无法找到解。需要撤销刚才的操作，以便尝试下一个方向：
        • 从 path 中移除最后一个字符。
        • 将 edge[a][b][x][y] 设为 false。
   • 失败: 如果尝试了所有 8 个方向都无法找到解，说明从 (a, b) 出发无法到达目标，将 (a, b) 标记为未访问（st[a][b] = false），然后返回 false。

3. 字典序最小:
   由于我们在 DFS 中总是按照方向 0 到 7 的顺序进行探索，那么我们找到的第一条完整路径必然是字典序最小的路径。因此，一旦找到解，就可以立即停止搜索并返回。

4. 初始调用:
   从起点 (0, 0) 开始调用 DFS：dfs(0, 0)。
   在调用前，需要确保起点 g[0][0] 的数字是 0 (虽然题目没有明确说明，但根据数字序列规则，起点必须是 0 才能开始)。如果 g[0][0] != 0，则不可能有解。

5. 结果处理:
   如果初始调用 dfs(0, 0) 返回 true，则输出 path。
   如果返回 false，则输出 -1。

6. 实现细节 (代码解读):

   • dx, dy 数组：存储 8 个方向的坐标偏移量，顺序对应方向编号 0 到 7。
   • path: 存储构建中的路径字符串。
   • st[n][n]: 布尔数组，st[i][j] 为 true 表示格子 (i, j) 当前在 DFS 路径上（已被访问）。
   • edge[n][n][n][n]: 4 维布尔数组，edge[r1][c1][r2][c2] 为 true 表示路径中包含了从 (r1, c1) 到 (r2, c2) 的移动。用于非交叉检查。
   • dfs 函数使用 C++11 的 lambda 表达式和 auto& self 实现递归。
   • 非交叉检查 if (i % 2 && (edge[a][y][x][b] || edge[x][b][a][y])) continue; 精确地实现了上述逻辑。
   • 回溯通过 path.pop_back() 和 edge[a][b][x][y] = false 以及最后将 st[a][b] = false 实现。

时间复杂度

状态空间是所有可能的路径。在最坏情况下，路径可能非常多。每个 DFS 状态需要尝试最多 8 个方向。路径的最大深度是 $N^2$。因此，粗略的上界是 $O(8^{N^2})$。然而，由于各种约束（特别是访问检查和数字序列检查），实际的搜索空间会小得多。但它仍然是指数级别的复杂度。对于 $N=10$，$N^2=100$，这个复杂度是可以接受的，因为很多分支会被快速剪枝。更精确的分析比较困难。可以认为是 $O(N^2 \times C)$，其中 C 是有效路径的数量，但 C 本身可能是指数级的。考虑到 $N \le 10$，该算法在时限内是可行的。

空间复杂度

• 递归调用栈深度：最坏情况下为 $O(N^2)$。
• st 数组：$O(N^2)$。
• edge 数组：$O(N^4)$。
• path 字符串：最多 $O(N^2)$。
• 总空间复杂度主要是 $O(N^4)$。对于 $N=10$，这是 $10^4$ 级别的，在内存限制内。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名 (虽然本题没用到)

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    int n, k; // 棋盘大小 N, 数字范围 K
    cin >> n >> k;

    // g[i][j] 存储棋盘上格子 (i, j) 的数字
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    // dx, dy 存储 8 个方向的坐标偏移
    // 0:上, 1:右上, 2:右, 3:右下, 4:下, 5:左下, 6:左, 7:左上
    int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
    int dy[] = {0, 1, 1, 1, 0, -1, -1, -1};

    string path; // 存储当前构建的路径字符串
    // st[i][j] 标记格子 (i, j) 是否在当前 DFS 路径上
    vector<vector<bool>> st(n, vector<bool>(n, false));
    // edge[r1][c1][r2][c2] 标记路径中是否存在从 (r1, c1) 到 (r2, c2) 的移动
    vector edge(n, vector<vector<vector<bool>>>(n, vector<vector<bool>>(n, vector<bool>(n, false))));

    // 定义 DFS 函数 (使用 lambda 表达式)
    // auto& self 用于在 lambda 内部递归调用自身
    auto dfs = [&](int a, int b, auto& self) -> bool {
        // 基础情况：到达右下角 (n-1, n-1)
        if (a == n - 1 && b == n - 1) {
            // 检查是否访问了所有格子 (路径长度是否为 n*n - 1)
            return path.size() == n * n - 1;
        }

        // 标记当前格子 (a, b) 为已访问
        st[a][b] = true;

        // 按 0 到 7 的顺序尝试 8 个方向，保证字典序最小
        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;
            // 检查移动合法性：非交叉检查 (仅对对角线移动 i%2 == 1)
            // 如果是对角线移动，检查潜在的交叉边 (a,y)->(x,b) 或 (x,b)->(a,y) 是否已存在
            if (i % 2 && (edge[a][y][x][b] || edge[x][b][a][y])) continue;

            // 移动合法，进行尝试
            edge[a][b][x][y] = true; // 记录移动边
            path += char(i + '0'); // 将方向加入路径字符串

            // 递归调用 DFS
            if (self(x, y, self)) return true; // 如果找到解，直接返回 true

            // 回溯：如果从 (x, y) 出发无法找到解，撤销操作
            path.pop_back(); // 移除路径中的最后一个方向
            edge[a][b][x][y] = false; // 取消记录移动边
        }

        // 如果所有方向都尝试失败，回溯当前格子的访问状态
        st[a][b] = false;
        return false; // 返回失败
    };

    // 从起点 (0, 0) 开始 DFS
    // (隐含假设: g[0][0] == 0)
    if (!dfs(0, 0, dfs)) { // 如果 DFS 返回 false (找不到路径)
        cout << -1 << "\n"; // 输出 -1
    } else { // 如果 DFS 返回 true (找到路径)
        cout << path << "\n"; // 输出找到的字典序最小路径
    }

    return 0; // 程序正常结束
}