题目内容

塔子哥是一名勇敢的冒险家，他一直梦想着找到传说中的黄金之城。他听说在一个遥远的沙漠中，有一个隐藏着无数宝藏的迷宫，只有最聪明和最勇敢的人才能进入并找到出路。塔子哥决定去挑战这个迷宫，他带着一张地图和一些装备，踏上了寻宝之旅。

但是，这个迷宫并不是那么容易通过的，它充满了各种危险和难题。除了一些隐藏在地面上的陷阱之外，还有一些时隐时现的墙壁，它们会随机地出现和消失，阻挡塔子哥的前进。塔子哥必须小心地观察墙壁的状态循环，绕过陷阱和墙壁，或者等待合适的时机通过。这是个 $n\times n$ 大小的迷宫，迷宫中存在着 $k$ 个陷阱，并且每个位置都存在着一个墙壁的状态循环，状态循环以 $3$ 个单位时间作为一个循环， $0$ 表示没有墙壁， $1$ 表示有墙壁。

塔子哥在每个单位时间可以向上、下、左、右某个方向移动一个地图单位,当然也可以选择原地踏步。

题面描述

塔子哥是一名勇敢的冒险家，他梦想找到传说中的黄金之城。在一个充满陷阱和随机出现墙壁的 $n * n$ 大小的迷宫中，他需要巧妙地避开这些障碍，才能找到宝藏。迷宫中有 $k$ 个陷阱，每个位置的墙壁状态以 $3$ 个单位时间循环变化，塔子哥每个单位时间可以选择移动或原地不动，但不能停在有墙壁或陷阱的位置。我们需要计算他找到宝藏的最短时间，如果无法到达宝藏，则输出 -1。

题解

塔子哥的迷宫挑战可以用广度优先搜索（BFS）来解决，但与普通的最短路径问题不同，本题涉及到一个状态维度，即墙壁的状态在时间上是周期性变化的。每个位置在每个时间单位可能会有不同的墙壁状态，因此我们需要使用三维数组来表示距离。

我们定义一个三维数组 dist[i][j][k]，表示到达坐标 (i, j) 且状态为 k 的最短时间。状态 k 的取值为 0, 1, 2，对应于时间的三个状态循环。每次移动时，塔子哥可以选择向四个方向移动，或选择原地不动，这种情况下，状态会随时间变化。