该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

裂墙券

题目描述

给定一个 $n \times m$ 的迷宫。

迷宫中每个格子可能是以下四种字符之一：

• .：空地；
• #：雾墙；
• S：起点；
• T：终点。

你一开始位于起点 S。

每次你可以向上、下、左、右相邻的格子移动一步，每移动一步耗时 $1$。

如果你要进入的格子是雾墙 #，则必须消耗 $1$ 张裂墙券才能进入。你一共有 $k$ 张裂墙券。

需要注意的是，裂墙券只对这一次进入生效，雾墙不会被永久拆除。也就是说，如果之后再次进入同一个雾墙格子，仍然需要再次消耗 $1$ 张裂墙券。

请你求出从 S 到 T 的最少移动次数。

如果无法到达终点，输出 -1。

输入格式

第一行输入三个整数 $n,m,k$，表示迷宫的行数、列数和裂墙券数量。

接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，表示迷宫。

数据范围

对于所有测试数据，满足：

• $1 \le n,m \le 1000$
• $2 \le n \times m \le 2 \times 10^5$
• $0 \le k \le 10$
• 迷宫中恰好有一个 S 和一个 T
• S 和 T 不是同一个格子
• 迷宫只包含字符 ., #, S, T

输出格式

输出一个整数，表示从 S 到 T 的最少移动次数。

如果无法到达，输出 -1。

输入输出样例 #1

输入 #1

3 5 1
S#..T
.#.#.
.....

输出 #1

4

输入输出样例 #2

输入 #2

3 5 1
S#.#T
...#.
.....

输出 #2

6

输入输出样例 #3

输入 #3

2 3 0
S#T
###

输出 #3

-1

说明/提示

样例 1 说明：

可以直接从第一行穿过雾墙到达终点：

S→#→.→.→T

一共移动 $4$ 步，使用 $1$ 张裂墙券。