洛谷 P10427：八方向不交叉路径——DFS、约束搜索与插头 DP

这是我记录的第一篇完整算法笔记。它不是只记“这题怎么过”，而是把源码里的每个数组、函数和剪枝都拆开：

二维数组
→ 访问标记
→ DFS / 回溯
→ 数字循环约束
→ 线段交叉判定
→ 剪枝
→ 字典序最小

1. 题目在做什么

给定一个 n × n 方阵，每个格子中有一个数字。数字按：

0, 1, ..., k - 1, 0, 1, ...

循环出现。

从左上角 (0, 0) 出发，每一步可以向八个相邻方向走：

上、右上、右、右下、下、左下、左、左上

要求：

  1. 走满全部 n² 个格子；
  2. 每个格子只能经过一次；
  3. 路径线段不能彼此交叉；
  4. 第 step 步踩到的数字符合循环规则；
  5. 最后停在右下角 (n - 1, n - 1)；
  6. 有多条合法路径时，输出字典序最小的方向序列；
  7. 无解时输出 -1。

从 n² 个格子出发并且不重复，实际移动次数是：

n² - 1

因此源码预留：

int ans[100];

来保存最多 99 次移动。

2. 先读懂全局变量

源码开头：

int n, k;
int a[10][10];
int vis[10][10];
int ans[100];
int ansLen = 0;
bool found = false;
变量 含义
n 方阵边长，决定坐标范围和总格子数
k 数字循环节，决定下一步需要的数字
a 输入的方阵数字
vis 访问标记，1 表示格子已经走过
ans 保存方向编号，而不是坐标
ansLen 当前路径已经走了多少条边
found 是否已经找到第一条完整答案

这几个变量共同构成 DFS 状态：

当前位置 (x, y)
+ 已走步数 step
+ 已访问格子 vis
+ 当前方向序列 ans[0..ansLen-1]

其中：

step == ansLen

在正常递归过程中始终成立。

3. 八个方向数组

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

将方向编号 d 代入 (x + dx[d], y + dy[d])：

d dx dy 方向
0 -1 0 上
1 -1 1 右上
2 0 1 右
3 1 1 右下
4 1 0 下
5 1 -1 左下
6 0 -1 左
7 -1 -1 左上

源码最后直接：

printf("%d", ans[i]);

所以当前程序输出的是方向编号 0~7 的数字序列，而不是 U、R、D 这类字符。理解题目输出格式时，要以题目要求和这组编号定义为准。

4. 步数和数字循环

从起点开始：

vis[0][0] = 1;
dfs(0, 0, 0);

这里 step = 0 表示：

现在站在起点，已经移动了 0 步。

在 dfs 中，准备走下一步时写：

int need = (step + 1) % k;

因为当前函数已经站在第 step 步的位置，检查的是即将走到的下一格。

起点单独检查：

if (a[0][0] != 0) {
    printf("-1\n");
    return 0;
}

源码把起点固定为数字 0；起点不满足时，不需要进入 DFS。

5. DFS 的终止条件

源码：

if (step == n * n - 1) {
    if (x == n - 1 && y == n - 1) {
        found = true;
    }
    return;
}

这里两个条件缺一不可：

  1. step == n * n - 1：已经覆盖全部 n² 个格子；
  2. x == n - 1 && y == n - 1：最后所在格子是右下角。

不能只判断终点坐标，也不能只判断步数。

6. DFS 的四个剪枝

每次尝试从 (x, y) 走到 (nx, ny)，源码依次检查：

6.1 出界

if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

6.2 不能重复访问

if (vis[nx][ny]) continue;

6.3 数字必须匹配

if (a[nx][ny] != need) continue;

6.4 新线段不能交叉

if (crosses(x, y, nx, ny)) continue;

四个条件的分工是：

出界       → 不能走出方阵
vis        → 不能重复格子
数字判断   → 必须满足题目节拍
crosses    → 线段不能相交

7. crosses() 的实际源码

bool crosses(int x1, int y1, int x2, int y2) {
    int px = 0, py = 0;

    for (int i = 0; i < ansLen; i++) {
        int d = ans[i];
        int nx = px + dx[d];
        int ny = py + dy[d];

        int mid1x = px + nx;
        int mid1y = py + ny;
        int mid2x = x1 + x2;
        int mid2y = y1 + y2;

        if (mid1x == mid2x && mid1y == mid2y) {
            if (!((px == x1 && py == y1 && nx == x2 && ny == y2) ||
                  (px == x2 && py == y2 && nx == x1 && ny == y1))) {
                return true;
            }
        }

        px = nx;
        py = ny;
    }

    return false;
}

这个函数不保存整条坐标路径，而是从起点 (0, 0) 出发，重新播放：

ans[0], ans[1], ..., ans[ansLen - 1]

恢复旧路径的每一条线段。

两条线段的中点相同，可以比较两倍中点：

px + nx == x1 + x2
&&
py + ny == y1 + y2

不用浮点数的原因是，所有端点坐标都是整数。

但同一条线段和自己当然共享中点，所以源码还排除了当前边和旧边正向或反向相同的情况：

中点相同
且
不是同一条边
→ 发生交叉

最典型的非法情况是两条对角线：

左上 → 右下
左下 → 右上

它们端点不同，但会穿过同一个正方形中心。

因此：

vis     负责端点不重复
crosses 负责线段中间不相交

可交互演示：拖动点观察中点与交叉

拖动 A、B，观察中点 M 如何随端点移动；打开“显示交叉”，可以看到两条对角线共享同一个中点，这正是 crosses() 需要拦截的情况。

8. DFS 回溯和状态撤销

通过所有剪枝后，源码把新格子和方向加入当前状态：

vis[nx][ny] = 1;
ans[ansLen++] = d;

dfs(nx, ny, step + 1);

递归失败后撤销：

ansLen--;
vis[nx][ny] = 0;

这就是回溯：

进入分支：借用一个格子，记录一个方向
递归失败：归还这个格子，删除这个方向
递归成功：保留整条答案

忘记任意一个撤销操作，都会污染后续分支。

9. 为什么第一条答案是字典序最小

源码固定按：

for (int d = 0; d < 8; d++)

枚举方向。只要方向编号 0~7 的顺序就是题目规定的字典序，DFS 就会先尝试字典序更小的前缀。

一旦找到完整路径：

found = true;

递归返回后立即：

if (found) return;

因此更大的方向分支不会覆盖答案。

这个结论有一个前提：

方向数组顺序、输出编号顺序和题目字典序必须一致。

10. 主函数的执行顺序

读取 n、k
    ↓
读取 n×n 方阵 a
    ↓
检查 a[0][0] 是否为 0
    ↓
标记 vis[0][0] = 1
    ↓
dfs(0, 0, 0)
    ↓
found 为真：输出 ans[0..ansLen-1]
found 为假：输出 -1

11. 源码完整版本

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

int n, k;
int a[10][10];
int vis[10][10];
int ans[100];
int ansLen = 0;
bool found = false;

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

bool crosses(int x1, int y1, int x2, int y2) {
    int px = 0, py = 0;
    for (int i = 0; i < ansLen; i++) {
        int d = ans[i];
        int nx = px + dx[d];
        int ny = py + dy[d];

        int mid1x = px + nx, mid1y = py + ny;
        int mid2x = x1 + x2, mid2y = y1 + y2;

        if (mid1x == mid2x && mid1y == mid2y) {
            if (!((px == x1 && py == y1 && nx == x2 && ny == y2) ||
                  (px == x2 && py == y2 && nx == x1 && ny == y1))) {
                return true;
            }
        }

        px = nx;
        py = ny;
    }
    return false;
}

void dfs(int x, int y, int step) {
    if (found) return;

    if (step == n * n - 1) {
        if (x == n - 1 && y == n - 1) {
            found = true;
        }
        return;
    }

    int need = (step + 1) % k;

    for (int d = 0; d < 8; d++) {
        int nx = x + dx[d];
        int ny = y + dy[d];

        if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
        if (vis[nx][ny]) continue;
        if (a[nx][ny] != need) continue;
        if (crosses(x, y, nx, ny)) continue;

        vis[nx][ny] = 1;
        ans[ansLen++] = d;

        dfs(nx, ny, step + 1);

        if (found) return;

        ansLen--;
        vis[nx][ny] = 0;
    }
}

int main() {
    scanf("%d %d", &n, &k);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &a[i][j]);

    // 起点必须是 0
    if (a[0][0] != 0) {
        printf("-1\n");
        return 0;
    }

    vis[0][0] = 1;
    dfs(0, 0, 0);

    if (found) {
        for (int i = 0; i < ansLen; i++)
            printf("%d", ans[i]);
        printf("\n");
    } else {
        printf("-1\n");
    }

    return 0;
}

12. 复杂度、边界和调试

不加限制时，每一步最多 8 个方向，粗略上界接近：

O(8^(n²))

这是指数级搜索。实际依靠出界、访问、数字和交叉四层剪枝缩小分支。

额外空间主要是：

a：O(n²)
vis：O(n²)
ans：O(n²)
递归栈：O(n²)

调试按这个顺序检查：

  1. a[0][0] 是否为 0；
  2. n、k 和矩阵是否读入正确；
  3. step 是否统一表示“已经移动的步数”；
  4. 下一步是否使用 (step + 1) % k；
  5. vis 是否递归前标记、失败后撤销；
  6. ansLen 是否与递归深度一致；
  7. crosses() 是否排除了同一条线段；
  8. 方向数组顺序是否符合字典序；
  9. 提交前删除调试输出。

13. 进阶解法一：约束传播 + 回溯

这一档的直觉是先把棋盘看成图，再根据每个点最终应该连接几条边，提前排除不可能的边：

起点、终点：度数 1
其它格子：度数 2

边可以暂时分成三种状态：

struct Edge {
    int u, v;
    int state;   // -1：禁用，0：未确定，1：必选
};

在只考虑“度数”的情况下，传播规则很自然：

已选边 > 目标度数       → 失败
可用边 < 目标度数       → 失败
可用边 == 目标度数      → 剩余边全部必选
已选边 == 目标度数      → 剩余边全部禁用

这部分确实是很有价值的图搜索思想：状态一改变，就立刻把确定结果传给相邻点，而不是等搜索走到最后才发现死局。

13.1 为什么这份“第一版解法”不能直接当成正确算法

这里必须特别标注：“候选边 + 无向度数传播”的草稿是不完整的，按原样实现不能保证 AC。 问题不在传播规则，而在于它丢掉了本题最重要的全局信息。

问题一：本题的数字条件依赖“步数”，不是只依赖相邻两个格子

题目的原条件是：从当前路径位置走到下一个格子时，目标格子的数字必须等于：

a[next] == step % k;

因此，边实际上有方向和时间含义。草稿中的：

a[v] == (a[u] + 1) % k

最多只能说明“这条边可能按 u -> v 方向走”。如果把它塞进无向 Edge {u, v}，就没有记录这条边最终是从谁走向谁，也没有记录它在完整路径中的第几步。

只满足点的度数，并不能推出从 (0,0) 出发时每一步的 step % k 都正确。

问题二：度数正确，不代表是一条覆盖全图的路径

即使满足：

起点度数 1、终点度数 1、其它点度数 2

选出的图仍可能是：

一条从起点到终点的路径 + 一个内部小环

或者是多个互不连通的路径片段。needDegree() 只能检查“每个点接了几条边”，不能检查“所有点是否属于同一条路径”。

问题三：并查集只能辅助查环，不能自动恢复路径顺序

加入边时用 DSU 检测提前闭环是必要的，但还不够。即使当前没有环，也可能形成多个连通分量；而且并查集只知道连通性，不知道从起点沿哪个方向走、走到每个点时是第几步。

因此，下面这种逻辑不能单独证明正确：

传播成功 + 没有提前成环 + 所有点度数满足
→ 一定存在题目要求的答案

结论是：第一版约束传播代码适合当作建模草图，不能直接替换现有的路径 DFS。

13.2 如果继续完善，至少要补哪些状态

要把这个方向做成真正的求解器，边不能只记录“选/不选”，还至少要补上：

  1. 方向：把无向候选边拆成有向弧，记录 u -> v 是否可用；
  2. 入度和出度：起点只能出、终点只能入，中间点需要一进一出；
  3. 连通分量：禁止内部小环和多个独立路径，必要时用可回滚 DSU；
  4. 交叉约束：选中一条对角线后，立刻禁用共享中点的另一条对角线；
  5. 前缀可行性：当前选出的有向边必须还能从起点按 step 顺序串成一条完整路径；
  6. 字典序：最终仍要按方向编号从小到大尝试，并确认这个前缀还能补完。

所以更准确的搜索框架应该是：

传播局部约束
→ 检查方向、度数、交叉和连通性
→ 选择最紧的未决边
→ 分支“选中 / 禁用”
→ 回溯

它比“沿当前端点 DFS”更全局，但实现难度也明显更高。学习时可以先只实现度数传播，再逐步加入方向和 DSU；每加一种状态，都要用小棋盘验证它是否真的排除了错误答案。

14. 进阶解法二：轮廓 DP / 插头 DP

插头 DP 的核心不是保存整个棋盘的 vis，而是按固定顺序扫描棋盘，只保留“已处理区域”和“未处理区域”的边界状态：

已经处理的格子 | 尚未处理的格子
█████████████ | ···········
█████████████ | ···········
----------------------------

左侧已经不会再被未来访问，真正影响后续决策的只有扫描线上的连接，因此状态规模可以从面积相关的指数压缩到宽度相关的指数。

14.1 插头状态保存什么

轮廓数组的每一格通常表示：

0：这里没有路径连接
非 0：这里有一条“插头”，并带有连通块编号

不能只用“左端 / 右端”两个标记。扫描过程中可能同时存在多个路径片段，必须用编号表示“哪些插头属于同一个连通块”，并在每次转移后做编号规范化：

原状态：0 7 0 7 3 0
规范化：0 1 0 1 2 0

这样相同的拓扑结构才能合并到同一个 DP 状态。

14.2 每个格子的转移

处理当前格子时，枚举它与已处理邻居、未处理邻居之间的连边方式，并检查：

  1. 当前格子的最终度数是否满足；
  2. 边的方向/数字条件是否满足；
  3. 是否与已选对角线共享中点而发生交叉；
  4. 是否把一个尚未完成的路径提前闭成环；
  5. 新状态的插头连接关系是否正确。

状态大致可以写成：

unordered_map<uint64_t, bool> dp, nextDp;

for (int pos = 0; pos < n * n; ++pos) {
    nextDp.clear();

    for (auto [state, reachable] : dp) {
        decode(state);

        for (auto choice : localChoices) {
            if (!degreeOK(choice)) continue;
            if (!digitOK(choice)) continue;
            if (!crossOK(choice)) continue;
            if (formsIllegalCycle(choice)) continue;

            uint64_t nextState = transition(state, choice);
            normalize(nextState);
            nextDp[nextState] = true;
        }
    }

    dp.swap(nextDp);
}

如果轮廓宽度不超过 11，可以把每个位置压成 4 bit：

int get(uint64_t state, int i) {
    return (state >> (i * 4)) & 15;
}

uint64_t setValue(uint64_t state, int i, int value) {
    state &= ~(15ULL << (i * 4));
    state |= static_cast<uint64_t>(value) << (i * 4);
    return state;
}

14.3 这道题使用插头 DP 的额外难点

普通四方向网格的插头 DP 不能直接套到本题，原因有三层：

  1. 本题允许八方向：对角边会跨越相邻行列，扫描线要保留更多边界信息；
  2. 本题禁止对角线交叉：两个不同端点的对角边可能共享同一个方格中心，必须把这个几何冲突纳入转移；
  3. 数字条件按路径步数变化：仅知道“两个格子相邻”还不够，还要知道路径方向以及路径片段的长度/顺序信息，不能只做无向连通性判断。

此外，插头 DP 本身只回答“当前状态是否还能完成”。题目还要求方向序列字典序最小，因此通常要分两阶段：

第一阶段：DP 判断某个前缀是否仍然可完成
第二阶段：从起点开始，按方向 0..7 逐个尝试
          选择第一个能被 DP 证明可完成的方向

这样每一步都选最小可行方向，最终才得到字典序最小答案。

14.4 两种进阶解法的定位

约束传播 + 回溯：更容易理解，适合学习图建模、度数约束、DSU 和启发式搜索；
插头 DP：状态压缩更强，但需要同时处理边界连通性、八方向、交叉和步数约束。

因此，当前这道题的学习顺序应当是：

现有路径 DFS
→ 正确的全局剪枝
→ 带方向/连通性的约束搜索
→ 最后再考虑插头 DP

不要把第一版“无向边 + 度数传播”的伪代码直接当成最终题解；它最适合用来理解“约束传播”这个思想，而不是直接提交。

一句话复习

P10427 的核心是：在八方向网格中用 DFS 回溯枚举路径；用 vis 保证格子不重复，用 crosses() 保证线段不交叉，用 (step + 1) % k 检查数字循环，并按方向编号从小到大搜索，第一条覆盖全部 n² 个格子且到达右下角的路径就是字典序最小答案。