算法标签

状态压缩动态规划、插头DP、哈希表

问题分析

本题要求统计满足特定条件的旅行路线数量，核心约束包括：路线需遍历所有展馆、相邻展馆必须相邻且未被访问、起点在矩阵边界、第i个参观的展馆类型需匹配给定01序列。

关键观察

• 矩阵规模小（(n \leq 3)，(m \leq 50)），适合用状态压缩动态规划处理。
• 需跟踪当前已访问展馆的顺序、插头状态（记录路径的延伸方向），因此采用插头DP模型，通过哈希表存储状态。

核心算法思路

1. 状态表示与编码

• 用num数组记录每行当前路径的序号，plug数组记录插头状态（0无插头、1递减插头、3递增插头）。
• 通过编码函数将num和plug的状态压缩为一个整数，利用哈希表unordered_map存储状态对应的路线数。

2. 状态转移

• 针对不同位置（边界、中间、起点、终点）和插头状态，分情况处理转移：
  • 插头合并：处理路径交汇的情况，确保序号和插头类型的合法性。
  • 新建插头：在起点、中间位置创建递增/递减插头，匹配01序列的当前要求。
  • 起点/终点处理：检查位置是否在矩阵边界，且序号为1或(n \times m)，同时匹配01序列。

3. 结果统计

遍历最终状态，统计所有合法的结束状态（无剩余插头）对应的路线数，取模得到结果。

复杂度分析

• 状态数由num和plug的可能组合决定，因(n \leq 3)、(m \leq 50)，状态数在可接受范围内。
• 时间复杂度为(O(n \times m \times S))（(S)为状态数），可满足题目数据范围。

总结

本题通过插头DP结合哈希表，高效处理了路径的状态跟踪和转移，利用状态压缩技术在小矩阵规模下实现了路线计数。核心是对插头状态和序号的精准管理，确保满足路径相邻、01序列匹配、起点边界等所有约束条件。