[蓝桥杯 2018 国 C] 迷宫与陷阱

题目描述

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

输入输出格式

输入格式


第一行包含两个整数 $N$ 和 $K$。$(1 \le N \le 1000,1 \le K \le 10)$。 以下 $N$ 行包含一个 $N\times N$ 的矩阵。 矩阵保证左上角和右下角是 `.`。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

10

输入样例 #2

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

输出样例 #2

12

说明

时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛