题目描述

本题使用文件输入输出：输入文件名为 wall.in，输出文件名为 wall.out。

一座 $n$ 行 $m$ 列的迷宫，每个格子是空地 .、墙 #、起点 S 或终点 T 之一（起点和终点各恰好一个，它们本身是空地）。

小 Z 从起点出发，每一步可以走到上、下、左、右相邻的一个格子，不能走出迷宫。小 Z 带着一把锤子，最多能砸开 $k$ 面墙：走进一个墙格子时，这面墙就被砸开，消耗一次机会；砸开后这个格子就变成空地。

请你求出从起点走到终点最少需要多少步。如果砸开至多 $k$ 面墙也无法到达终点，输出 $-1$。

输入格式

输入文件名为 wall.in。

第一行三个整数 $n, m, k$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述迷宫。

输出格式

输出文件名为 wall.out。

一行一个整数，表示最少步数；无法到达输出 $-1$。

样例 #1

样例输入 #1

3 4 1
S#..
##.#
...T

样例输出 #1

5

样例解释

起点 $(1,1)$ 的右边和下边都是墙，必须砸一面。例如砸开 $(2,1)$：$(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3) \to (3,4)$，共 $5$ 步。砸开 $(1,2)$ 走上面一条路也是 $5$ 步。

样例 #2

样例输入 #2

3 4 0
S#..
##.#
...T

样例输出 #2

-1

样例 #3

样例输入 #3

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

样例输出 #3

4

样例解释

不砸墙要绕到第 $3$ 行，需要 $6$ 步；砸开 $(1,3)$ 直接横穿只要 $4$ 步。

提示

数据范围

• 对于 $30\%$ 的数据：$k = 0$；
• 对于 $60\%$ 的数据：$n, m \le 50$，$k \le 5$；
• 对于 $100\%$ 的数据：$1 \le n, m \le 500$，$0 \le k \le 10$。