P1399 - [蓝桥杯2018决赛]迷宫与陷阱

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：531 通过：120

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由NxN个格子组成的2D迷宫。
小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。
每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。
迷宫中有些格子小明可以经过，我们用'.'表示；
有些格子是墙壁，小明不能经过，我们用'#'表示。
此外，有些格子上有陷阱，我们用'X'表示。除非小明处于无敌状态，否则不能经过。
有些格子上有无敌道具，我们用'%'表示。
当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续K步。
之后如果再次到达该格子不会获得无敌状态了。
处于无敌状态时，可以经过有陷阱的格子，但是不会拆除/毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。
给定迷宫，请你计算小明最少经过几步可以离开迷宫

输入包含多组测试数据，对于每组测试数据：
第一行包含两个整数N和K。 (1 <= N <= 1000 1 <= K <= 10)
以下N行包含一个NxN的矩阵。矩阵保证左上角和右下角是'.'。

对于每组测试数据输出一行包含一个整数表示答案。
如果小明不能离开迷宫，输出-1。

5 3
...XX
##%#.
...#.
.###.
.....
5 1
...XX
##%#.
...#.
.###.
.....

10
12

1399: [蓝桥杯2018决赛]迷宫与陷阱

题目描述

输入格式

输出格式

输入样例复制

输出样例复制