CJDF07｜限时迷宫 题解

核心算法

DFS 枚举不重复路径，并使用曼哈顿距离与奇偶性剪枝。

思路推导

到达当前格时已走 used 步，还剩 remain=k-used 步。设当前位置到终点的曼哈顿距离为 dist：若 dist>remain，剩余步数不够；若 remain-dist 为奇数，也不可能恰好到达，因为每次绕行会额外消耗偶数步。两种情况均可立即停止。

正确性说明

未被剪去的分支由 DFS 完整枚举。距离剪枝只删除必然走不够的状态；奇偶剪枝只删除步数奇偶不可能匹配的状态，二者都不会删除可行解。访问标记与恢复保证枚举的恰是所有不重复路径。

复杂度

最坏时间复杂度为指数级，深度不超过 $k$；空间复杂度 $O(nm+k)$。剪枝与题目规模共同保证可运行。

易错点

• 题目要求“恰好” $k$ 步，不是至多 $k$ 步；
• remain-dist 的奇偶性可以提前判定；
• 返回上一层时必须恢复访问标记；
• $k=0$ 时只有起点等于终点才可行。