### 问题描述 在一个古老的城市地下，考古学家发现了一座巨大的迷宫。这个迷宫据说有一个秘密室，里面藏有无价之宝。考古学家希望你帮助他们找到从迷宫的入口 `S` 到秘密室 `E` 的路径。 迷宫表示为一个 $n \times m$ 的矩阵： - `.` 表示一个可以走的空地。 - `#` 表示一个墙，不能走。 - `S` 表示开始位置。 - `E` 表示结束位置。 - `T` 表示一个定时的陷阱。当考古学家进入一个 `T` 位置，他们必须在接下来的 $k$ 步之内到达 `E`，否则陷阱会启动，导致失败。 您的任务是确定从 `S` 到 `E` 的最短路径。如果存在多个最短路径，您需要输出路径中经过的 `T` 的最小数量。 请注意：每个陷阱的触发和步数统计都是独立的，多次通过陷阱并不会刷新已存在的计数器！ ### 输入格式 输入的第一行包含三个整数 $n$, $m$ 和 $k$，$(1 \leq n, m \leq 500$，$1 \leq k \leq 10^4)$，分别表示地图的行数、列数和陷阱的有效步数。 接下来的 $n$ 行每行有 $m$ 个字符，描述地下迷宫的地图。 ### 输出格式 如果能够从 `S` 到 `E` ，输出一个整数，表示从 `S` 到 `E` 的最短路径长度。 如果无法到达 `E`，则输出 $-1$。 ### 样例输入 ``` 5 5 3 ..... .T#T. .S#E. .T##. ..... ``` ### 样例输出 ``` 8 ``` ### 样例说明 从 `S` 开始，我们可以先向左走，然后上走 $2$ 步，再右走 $3$ 步，下走两步到达 `E`。总共走了 $8$ 步，期间经过了第 $2$ 行第 $4$ 行的一个陷阱 `T`。 ### 测评数据规模 对于 $40$% 的数据，$1 \leq n, m \leq 10$。 对于 $80$% 的数据，$1 \leq n, m \leq 100$。 对于 $100$% 的数据，$1 \leq n, m \leq 500$。