题面描述

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

题解

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

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

题目内容

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

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

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

限制:如果小明移动方向上有陷阱，或者小明移动目的地在下一个单位时间出现墙壁，则不可以朝该方向移动，同时，如果小明当前位置在下一个单位时间会出现墙壁，那小明也不可以选择停在原地。

我们需要计算出小明找到宝藏的最短时间。注意，小明可能并到不了目的地哦，这种情况输出-1

输入描述

输入第一行为一个整数 $n$ ，表示迷宫的大小。（ $2<= n <= 100$ )

输入第二行为一个整数 $k$ ，表示迷宫中陷阱的数量。（ $0<k <= n\times n-2$ ）

接下来输入一行 $2\times k$ 个整数,具体为 $row_1\ col_1\ row_2\ col_2\ ...\ row_k\ col_k$ ，表示位置( $row_i$ , $col_i$ )存在一个陷阱。

接下来一行为两对整数（ $row1$ , $col1$ ) 和 ( $row2$ , $col2$ )，表示宝藏的位置和小明的起始位置。

然后接下来 $n$ 行: 每行 $n$ 个字符串空格分开，每个字符串长度固定为 $3$ ，内容固定只有 $0$ 和 $1$ ，表示每个位置的墙壁的状态循环。

注意 ：地图左上角为(0,0)，输入保证所有位置合法

输出描述

输出一个整数，表示小明找到宝藏的最短时间。

样例

样例一

输入

3
2
1 0 1 2
2 1 2 0
100 100 100
100 000 100
000 000 001

输出

1

样例解释

小明最快的移动顺序： [2,0] ->[2,1]

样例二

输入

3
2
1 0 2 0
0 1 2 2
000 000 001
010 101 101
110 010 000

输出

5

样例解释

小明最快的移动顺序： [2,2] ->[1,2] ->[2,2] ->[2,1] ->[1,1] ->[0,1]