题目描述

迷宫含起点 S、终点 T、钥匙 K、门 D、空地 . 和障碍 #。拿到钥匙后才能经过门。求到达终点的最少步数；无解输出 -1。

输入格式

第一行 $n,m$，随后 $n$ 行迷宫。保证恰有一个 S、T、K，门可以有多个。

输出格式

输出最少步数或 -1。

样例

3 5
S.D.T
.#.#.
..K..

8

数据规模与约定

$1\le n,m\le300$。