钥匙迷宫（key）

题目描述

$\text{DAMON THRONE}$ 的训练系统生成了一个 $n$ 行 $m$ 列的机关迷宫。

迷宫中的每个格子可能是：

• $\texttt{.}$：空地，可以经过；
• $\texttt{\#}$：墙壁，不能经过；
• $\texttt{S}$：起点；
• $\texttt{T}$：终点；
• $\texttt{a}\sim\texttt{j}$：钥匙；
• $\texttt{A}\sim\texttt{J}$：门。

小 D 从起点 $\texttt{S}$ 出发，每一步可以向上、下、左、右相邻格子移动一格。

如果小 D 走到某个钥匙格子，例如 $\texttt{c}$，就会获得钥匙 $\texttt{c}$。

如果小 D 想进入某个门格子，例如 $\texttt{C}$，则必须已经拥有钥匙 $\texttt{c}$。

钥匙获得后不会丢失，可以重复使用。

请你求出小 D 从 $\texttt{S}$ 到 $\texttt{T}$ 的最少步数。

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

输入格式

第一行包含三个整数 $n,m,K$，表示迷宫行数、列数和钥匙种类数。

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

保证迷宫中恰好有一个 $\texttt{S}$ 和一个 $\texttt{T}$。

迷宫中只会出现前 $K$ 种钥匙和门，即：

以及：

输出格式

输出一行一个整数。

如果可以到达终点，输出最少步数；否则输出 $-1$。

输入输出样例 #1

输入 #1

4 5 2
S.a#.
##A#.
.b.BT
.....

输出 #1

8

样例解释 #1

一种最优路线为：

先从 $\texttt{S}$ 出发拿到钥匙 $\texttt{a}$，打开门 $\texttt{A}$ 后继续前进，再绕到下方拿到钥匙 $\texttt{b}$，最后打开门 $\texttt{B}$ 到达 $\texttt{T}$。

最少需要 $8$ 步。

输入输出样例 #2

输入 #2

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

输出 #2

-1

数据范围与约定

对于所有测试数据，保证：

并保证：

特殊性质 $\text{A}$：保证迷宫中没有钥匙和门。

特殊性质 $\text{B}$：保证迷宫中没有墙壁 $\texttt{\#}$。

特殊性质 $\text{C}$：保证每种钥匙最多出现一次。