#P1572. 2023.05.06-暑期实习-第三题-黄金之城寻宝
-
ID: 20
Type: Default
1000ms
256MiB
Tried: 73
Accepted: 19
Difficulty: 6
Uploaded By:
TaZi
Tags>BFS
2023.05.06-暑期实习-第三题-黄金之城寻宝
题目内容
塔子哥是一名勇敢的冒险家,他一直梦想着找到传说中的黄金之城。他听说在一个遥远的沙漠中,有一个隐藏着无数宝藏的迷宫,只有最聪明和最勇敢的人才能进入并找到出路。塔子哥决定去挑战这个迷宫,他带着一张地图和一些装备,踏上了寻宝之旅。
但是,这个迷宫并不是那么容易通过的,它充满了各种危险和难题。除了一些隐藏在地面上的陷阱之外,还有一些时隐时现的墙壁,它们会随机地出现和消失,阻挡塔子哥的前进。塔子哥必须小心地观察墙壁的状态循环,绕过陷阱和墙壁,或者等待合适的时机通过。这是个 n×n 大小的迷宫,迷宫中存在着 k 个陷阱,并且每个位置都存在着一个墙壁的状态循环,状态循环以 3 个单位时间作为一个循环, 0 表示没有墙壁, 1 表示有墙壁。
塔子哥在每个单位时间可以向上、下、左、右某个方向移动一个地图单位,当然也可以选择原地踏步。
限制:如果塔子哥移动方向上有陷阱,或者塔子哥移动目的地在下一个单位时间出现墙壁,则不可以朝该方向移动,同时,如果塔子哥当前位置在下一个单位时间会出现墙壁,那塔子哥也不可以选择停在原地。
我们需要计算出塔子哥找到宝藏的最短时间。注意,塔子哥可能并到不了目的地哦,这种情况输出-1
输入描述
输入第一行为一个整数 n ,表示迷宫的大小。( 2<=n<=100 )
输入第二行为一个整数 k ,表示迷宫中陷阱的数量。( 0<k<=n×n−2 )
接下来输入一行 2×k 个整数,具体为 row1 col1 row2 col2 ... rowk colk ,表示位置( rowi , coli )存在一个陷阱。
接下来一行为两对整数( 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]
通知
扫码备注华为交流群~期待您的到来
- 湘ICP备2023007293号
- Worker 0, 23ms
- Powered by Hydro v4.14.1 Community