U386147 【MC系列7】走迷宫2
题目背景
## 题目提供者：[liu3600](https://www.luogu.com.cn/user/750365)
### [上期回顾](https://www.luogu.com.cn/problem/U386682)
### liu3600 又来走 GG_and_go_to_died 为他设计的独家迷宫了，但他知道，这迷宫绝对像上次那样有猫腻，于是想让你帮他看看能不能走出去。
~~走不出去还是挖出去~~
题目描述
liu3600 的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。
每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。
迷宫中有些格子 liu3600 可以经过，我们用 `.` 表示；
有些格子是墙壁，liu3600 不能经过，我们用 `#` 表示。
此外，有些格子上有陷阱，我们用 `X` 表示。除非 liu3600 处于无敌状态，否则不能经过。
有些格子上有无敌道具，我们用 `%` 表示。
当 liu3600 第一次到达该格子时，自动获得无敌状态，无敌状态会持续 $K$ 步。
之后如果再次到达该格子不会获得无敌状态了。
处于无敌状态时，可以经过有陷阱的格子，但是不会拆除 / 毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。
给定迷宫，请你计算 liu3600 最少经过几步可以离开迷宫。
输入格式
无
输出格式
无
说明/提示
$1 \le N \le 1000，1 \le K \le 10$