Dotcpp  >  编程题库  >  蓝桥杯2018年第九届真题-迷宫与陷阱
题目 2295:

蓝桥杯2018年第九届真题-迷宫与陷阱

时间限制: 1s 内存限制: 128MB 提交: 1337 解决: 266

题目描述

小明在玩一款迷宫游戏,在游戏中他要控制自己的角色离开一间由NxN个格子组成的2D迷宫。  
小明的起始位置在左上角,他需要到达右下角的格子才能离开迷宫。
每一步,他可以移动到上下左右相邻的格子中(前提是目标格子可以经过)。
迷宫中有些格子小明可以经过,我们用'.'表示;
有些格子是墙壁,小明不能经过,我们用'#'表示。
此外,有些格子上有陷阱,我们用'X'表示。除非小明处于无敌状态,否则不能经过。

有些格子上有无敌道具,我们用'%'表示。
当小明第一次到达该格子时,自动获得无敌状态,无敌状态会持续K步。
之后如果再次到达该格子不会获得无敌状态了。  

处于无敌状态时,可以经过有陷阱的格子,但是不会拆除/毁坏陷阱,即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫,请你计算小明最少经过几步可以离开迷宫

输入格式

第一行包含两个整数N和K。 (1 <= N <= 1000 1 <= K <= 10)  
以下N行包含一个NxN的矩阵。
矩阵保证左上角和右下角是'.'。

输出格式

一个整数表示答案。如果小明不能离开迷宫,输出-1。

样例输入

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

样例输出

10

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签