#P1572. 2023.05.06-暑期实习-第三题-黄金之城寻宝

2023.05.06-暑期实习-第三题-黄金之城寻宝

题目内容

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

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

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

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

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

输入描述

输入第一行为一个整数 nn ,表示迷宫的大小。( 2<=n<=1002<= n <= 100 )

输入第二行为一个整数 kk ,表示迷宫中陷阱的数量。( 0<k<=n×n20<k <= n\times n-2

接下来输入一行 2×k2\times k 个整数,具体为 row1 col1 row2 col2 ... rowk colkrow_1\ col_1\ row_2\ col_2\ ...\ row_k\ col_k ,表示位置( rowirow_i , colicol_i )存在一个陷阱。

接下来一行为两对整数( row1row1 , col1col1 ) 和 ( row2row2 , col2col2 ),表示宝藏的位置和塔子哥的起始位置。

然后接下来 nn 行: 每行 nn 个字符串空格分开,每个字符串长度固定为 33 ,内容固定只有 0011 ,表示每个位置的墙壁的状态循环。

注意 :地图左上角为(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]