迷宫冒险：题解

思路

同一层的单元格之间没有墙，最短路就是曼哈顿距离。若起点层数小于终点层数，路径必须依次穿过中间的每一道层间墙；每层只有顶门和右门两个选择，因此跨越一段连续层的最短路可以表示为一个 $2\times2$ 的最短路转移矩阵。

设 $D_i[j][k]$ 表示从第 $i$ 层第 $j$ 扇门的内侧单元格出发，穿过这扇门并在第 $i+1$ 层内走到第 $k$ 扇门内侧单元格的距离。门的外侧单元格分别是顶门坐标向上移动一格、右门坐标向右移动一格，所以 $D_i$ 可直接用曼哈顿距离计算。

两个连续区间的转移矩阵用 min-plus 乘法合并：

做法

子任务 1 直接在 $n^2$ 个单元格上 BFS，并只允许通过给定门跨层。

子任务 2 对每次询问，从起点层开始依次应用每一层的 $2\times2$ 转移，复杂度为 $O(nm)$。

满分做法对转移矩阵建立倍增表。询问时先计算起点到所在层两扇门的距离，再按二进制分解层数差应用矩阵，最后从终点层前一层的两扇门跨墙到终点。若两点同层则直接输出曼哈顿距离。

复杂度

预处理时间和空间复杂度均为 $O(n\log n)$。每次询问时间复杂度为 $O(\log n)$，额外空间复杂度为 $O(1)$。