专栏文章

题解：B4299 [蓝桥杯青少年组国赛 2022] 路线

RRootSign
B4299题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0exqx
此快照首次捕获于
2025/12/01 18:31
3 个月前
此快照最后确认于
2025/12/01 18:31
3 个月前
查看原文

路线 - 插头 DP 题解

题意简述

给定 m×nm \times n 的花盆矩阵，需要从左上角 (0,0)(0, 0) 出发，经过每个花盆恰好一次后返回起点。只能沿上下左右四个方向移动，求满足条件的路径总数。

问题分析

这是一个经典的哈密顿回路计数问题。在 m×nm \times n 的网格图中，需要找到一条从左上角出发、经过所有格子恰好一次、最后返回左上角的回路，并统计所有这样的回路数量。
由于 m,n≤11m, n \leq 11，格子总数最多为 121121，暴力搜索的复杂度为 O(4mn)O(4^{mn})，显然不可行。注意到网格图的特殊性质，我们可以使用插头 DP（也称轮廓线 DP 或基于连通性状态压缩的 DP）来高效求解。

算法思路

插头 DP 基本原理

插头 DP 是在网格图上进行动态规划的一种方法。核心思想是：
  1. 按顺序处理格子：按照从左到右、从上到下的顺序处理每个格子。
  2. 轮廓线：当前格子左边和上边的边界称为"轮廓线"，它将已处理格子和未处理格子分开。
  3. 插头：轮廓线与路径的交点称为"插头"。如果某条边上有路径经过，则该位置有插头；否则无插头。
  4. 状态压缩：用一个数组 code[0..n] 表示轮廓线上各位置的插头状态，其中：
    • code[j] 表示格子 (i,j)(i,j) 左边的插头
    • code[j+1] 表示格子 (i,j)(i,j) 上边的插头

连通性表示 - 括号序列

为了保证路径不出现分叉和环（除了最终的完整回路），我们需要维护路径的连通性。使用括号序列来表示：
  • 0：无插头
  • 1：左括号 (
  • 2：右括号 )
括号序列保证了以下性质：
  • 每个连通分量对应一对匹配的括号
  • 左括号标记连通分量的起点，右括号标记终点
  • 不会形成非法的环路

状态转移

对于当前格子 (i,j)(i, j)，根据左插头 left 和上插头 up 的不同组合，有以下转移：

情况 1：无插头 (0,0)(0, 0) → 创建新连通分量

如果右边和下边都有格子，可以创建一个新的 L 型连通分量：
CPP
┌─  设置：下插头 = 1（左括号）
│        右插头 = 2（右括号）

情况 2：单个插头 (0,p)(0, p) 或 (p,0)(p, 0) → 延伸插头

将现有插头向右或向下延伸：
  • 向右延伸：右插头继承该插头值
  • 向下延伸：下插头继承该插头值

情况 3：左括号 + 左括号 (1,1)(1, 1) → 合并连通分量起点

CPP
(  (  →  需要找到上插头配对的右括号，
└──┘     将其改为左括号，合并两个连通分量

情况 4：右括号 + 右括号 (2,2)(2, 2) → 合并连通分量终点

CPP
)  )  →  需要找到左插头配对的左括号，
└──┘     将其改为右括号，合并两个连通分量

情况 5：右括号 + 左括号 (2,1)(2, 1) → 连接路径

两个插头直接消失，形成一条连续路径。

情况 6：左括号 + 右括号 (1,2)(1, 2) → 形成回路

CPP
(···)  只有在右下角最后一个格子，
└───┘  且轮廓线上无其他插头时才合法

哈希表优化

使用哈希表存储状态，避免枚举所有 4n+14^{n+1} 个可能状态。只保留实际出现的状态，大幅降低空间和时间复杂度。

关键代码片段

状态编码与解码：
CPP
// 将轮廓线状态数组编码为整数（4进制）
int encode(int len) {
    int st = 0;
    for (int i = len; i >= 0; i--) {
        st = st * 4 + code[i];
    }
    return st;
}

// 将整数状态解码为轮廓线状态数组
void decode(int st, int len) {
    for (int i = 0; i <= len; i++) {
        code[i] = st % 4;
        st /= 4;
    }
}
查找配对括号：
CPP
int findMatch(int pos, int len) {
    int cnt = 0;
    if (code[pos] == 1) { // 左括号向右找
        for (int i = pos + 1; i <= len; i++) {
            if (code[i] == 1) cnt++;
            if (code[i] == 2) {
                if (cnt == 0) return i;
                cnt--;
            }
        }
    } else { // 右括号向左找
        for (int i = pos - 1; i >= 0; i--) {
            if (code[i] == 2) cnt++;
            if (code[i] == 1) {
                if (cnt == 0) return i;
                cnt--;
            }
        }
    }
    return -1;
}
状态转移核心代码：
CPP
int left = code[j], up = code[j + 1];

// 情况1：创建新连通分量
if (left == 0 && up == 0) {
    if (i + 1 < m && j + 1 < n) {
        code[j] = 1;
        code[j + 1] = 2;
        dp[nxt].insert(encode(n), ways);
        code[j] = code[j + 1] = 0;
    }
}
// 情况2：延伸插头
else if (left == 0 || up == 0) {
    int plug = (left != 0) ? left : up;
    if (j + 1 < n) { // 向右
        code[j] = 0;
        code[j + 1] = plug;
        dp[nxt].insert(encode(n), ways);
        code[j + 1] = up;
    }
    if (i + 1 < m) { // 向下
        code[j] = plug;
        code[j + 1] = 0;
        dp[nxt].insert(encode(n), ways);
        code[j] = left;
        code[j + 1] = up;
    }
}
// 情况3：合并起点
else if (left == 1 && up == 1) {
    int pos = findMatch(j + 1, n);
    code[j] = code[j + 1] = 0;
    code[pos] = 1;
    dp[nxt].insert(encode(n), ways);
    code[j] = left;
    code[j + 1] = up;
    code[pos] = 2;
}
// 情况4：合并终点
else if (left == 2 && up == 2) {
    int pos = findMatch(j, n);
    code[j] = code[j + 1] = 0;
    code[pos] = 2;
    dp[nxt].insert(encode(n), ways);
    code[j] = left;
    code[j + 1] = up;
    code[pos] = 1;
}
// 情况5：连接路径
else if (left == 2 && up == 1) {
    code[j] = code[j + 1] = 0;
    dp[nxt].insert(encode(n), ways);
    code[j] = left;
    code[j + 1] = up;
}
// 情况6：形成回路
else if (left == 1 && up == 2) {
    if (i == m - 1 && j == n - 1) {
        bool allZero = true;
        for (int p = 0; p <= n; p++) {
            if (p != j && p != j + 1 && code[p] != 0) {
                allZero = false;
                break;
            }
        }
        if (allZero) {
            code[j] = code[j + 1] = 0;
            dp[nxt].insert(encode(n), ways);
            code[j] = left;
            code[j + 1] = up;
        }
    }
}
换行处理：
CPP
// 轮廓线向下移动一行，所有插头状态右移
for (int k = 0; k < dp[cur].size; k++) {
    decode(dp[cur].state[k], n);
    for (int j = n; j >= 1; j--) {
        code[j] = code[j - 1];
    }
    code[0] = 0; // 最左边补0
    dp[cur].state[k] = encode(n);
}

答案处理

最终答案需要乘以 22，原因如下：
题目要求从左上角出发并返回左上角。我们的 DP 统计的是经过左上角的回路数。对于每个回路，从左上角出发有两个方向：
  1. 先向右走
  2. 先向下走
这两种走法对应同一个回路的不同遍历顺序，因此答案为 dp[0][0] × 2。

复杂度分析

  • 时间复杂度：O(mn⋅S⋅n)O(mn \cdot S \cdot n)，其中 SS 是每个格子处理时的状态数。实际状态数远小于 4n+14^{n+1}，通过哈希表优化后效率很高。
  • 空间复杂度：O(S)O(S)，使用滚动数组优化，只需存储当前和下一个状态集合。

完整代码

完整代码请参考：洛谷云剪贴板
核心框架如下：
CPP
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

#define endl '\n'

const int N = 12;
const int S = 1000000;

int m, n;
int code[N];

struct HashMap {
    int head[S], next[S], state[S];
    i64 val[S];
    int size;

    void init() {
        size = 0;
        memset(head, -1, sizeof(head));
    }

    void insert(int st, i64 v) {
        int h = st % S;
        for (int i = head[h]; i != -1; i = next[i]) {
            if (state[i] == st) {
                val[i] += v;
                return;
            }
        }
        state[size] = st;
        val[size] = v;
        next[size] = head[h];
        head[h] = size++;
    }
} dp[2];

// encode, decode, findMatch 函数如上所示

void solve() {
    cin >> m >> n;

    int cur = 0, nxt = 1;
    dp[cur].init();
    dp[cur].insert(0, 1);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            dp[nxt].init();

            for (int k = 0; k < dp[cur].size; k++) {
                decode(dp[cur].state[k], n);
                i64 ways = dp[cur].val[k];

                int left = code[j];
                int up = code[j + 1];

                // 6种情况的状态转移（详见上文代码片段）
            }

            swap(cur, nxt);
        }

        // 换行处理（详见上文代码片段）
    }

    i64 ans = 0;
    for (int i = 0; i < dp[cur].size; i++) {
        if (dp[cur].state[i] == 0) {
            ans = dp[cur].val[i];
            break;
        }
    }

    cout << ans * 2 << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

总结

本题适合用来学习插头 DP 的基本思想。解题关键在于：
  1. 理解插头 DP 的轮廓线和插头概念。
  2. 使用括号序列维护路径的连通性。
  3. 正确处理 66 种状态转移情况。
  4. 使用哈希表优化存储，避免枚举无效状态。
  5. 注意答案需要乘以 22，因为从起点出发有两个方向。
建议初学者先理解插头 DP 的基本思想，再逐步实现代码。可以参考陈丹琦的《基于连通性状态压缩的动态规划问题》论文深入学习。

参考资料

陈丹琦《基于连通性状态压缩的动态规划问题》

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...