F-迷宫穿越_河南萌新联赛2025第（六）场：郑州大学

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

你被困在一个大小为 $N \times M$ 的迷宫中, 迷宫的左上角坐标是 $(1, 1)$ , 右下角是 $(N, M)$ 。迷宫由空地 (用 '.' 表示) 和障碍物 (用 '#' 表示) 组成。你当前位于起点 $(1, 1)$ , 目标是到达终点 $(N, M)$ 。

你每次可以花费 1 分钟的时间, 从当前单元格移动到上、下、左、右四个相邻的单元格之一。

幸运的是, 你身上携带着 $K$ 张瞬移卷轴。当你准备移动到一个相邻的单元格时:

1.如果目标单元格是空地, 你可以正常移动过去, 这会花费 1 分钟。

2.如果目标单元格是障碍物, 你可以消耗一张瞬移卷轴, 强行移动到该障碍物单元格上。这个过程同样花费 1 分钟。一旦你离开了这个障碍物格子, 它对你来说仍然是障碍物。

每张瞬移卷轴只能使用一次。请问, 从起点 $(1, 1)$ 到达终点 $(N, M)$ 所需的最短时间是多少分钟? 如果无法到达, 请输出 $-1$ 。
注意: 起点 $(1, 1)$ 和终点 $(N, M)$ 保证是空地。

输入描述:

第一行包含三个整数  (, )。

接下来  行, 每行一个长度为  的字符串, 描述迷宫的布局。

输出描述:

输出一个整数, 表示从  到达  的最短时间。如果无法到达, 则输出 。

示例1

输入

复制

4 5 1
...##
.#...
.##.#
...#.

输出

复制

说明

最短路径的步数是 7，具体路径如下：
从 (0,0) 向下移动到 (1,0)。
从 (1,0) 向下移动到 (2,0)。
从 (2,0) 向下移动到 (3,0)。
从 (3,0) 向右移动到 (3,1)。
从 (3,1) 向右移动到 (3,2)。
从 (3,2) 向右移动到 (3,3)。在 (3,3) 处遇到障碍物 #。此时使用卷轴，穿过障碍物，到达 (3,3)。这是消耗了卷轴的一步。
从 (3,3) 向右移动到终点 (3,4)。
总共走了 7 步，并且使用了唯一的卷轴。