题目描述

话说，年轻的斯巴达勇士们终于走出迷宫，取得胜利并顺利赶了回来。可是等他们回到斯巴达的时候才发现，雅典人趁他们不在偷袭了城邦，并抓走了他们的臣民。侥幸逃出来的几个人说，他们被关押在一个迷宫的牢房里，并把关押他们的迷宫里的情况告诉了年轻的勇士：迷宫中的 S 点表示迷宫的入口，T 点表示迷宫中牢房的位置，. 表示空地，可以通过，# 表示墙，不能直接通过，K 表示陷阱，一旦进入就必死无疑。每次只能向上下左右四个方向移动，每移动一个单位距离需要耗费一个单位时间，所有斯巴达勇士的移动速度相同。

又是迷宫！！！这次斯巴达的勇士们彻底愤怒了！What’s more, today is the Magpie Festival！

由于斯巴达的勇士们无比愤怒，而且他们也想尽可能的在今天就能救出他们的臣民。所以当他们在迷宫中遇到墙的阻碍时，也能破墙进入。不过破墙的过程会花费一个单位的时间。现在请你计算一下他们最短需要多少时间才能找到迷宫的牢房。

PS：假设迷宫中每个点可以容纳的人数没有限制，所有勇士都是一起行动的，他们每次会一起向同一个方向移动。

输入格式

第一行：两个整数 $n, m$（$2 \le m \le n \le 20$），分别代表迷宫的行数和列数。 接下来 $n$ 行：每行 $m$ 个字符用来表示迷宫地图。

输出格式

输出一个整数，表示找到迷宫牢房的最短时间；如不能找到牢房，输出 -1。

样例 #1

样例输入 #1

3 4
S#.#
..K.
KKT.

样例输出 #1

8

样例解释 #1

我们将迷宫坐标化（行号从 1 到 3，列号从 1 到 4）：

• 入口 S 在 $(1,1)$，牢房 T 在 $(3,3)$；
• 墙 # 位于 $(1,2),(1,4)$；
• 陷阱 K 位于 $(2,3),(3,1),(3,2)$；
• 其余为空地 .。

移动规则：

• 移动到空地、入口或牢房：时间 $+1$；
• 移动到墙：需破墙，时间 $+2$（移动 $1$ + 破墙 $1$）；
• 陷阱无法进入。

最短路径说明（总时间 8）：

1. $(1,1) \to (1,2)$：墙，破墙，时间累计 $2$；
2. $(1,2) \to (1,3)$：空地，时间累计 $3$；
3. $(1,3) \to (1,4)$：墙，破墙，时间累计 $5$；
4. $(1,4) \to (2,4)$：空地，时间累计 $6$；
5. $(2,4) \to (3,4)$：空地，时间累计 $7$；
6. $(3,4) \to (3,3)$：牢房 T，时间累计 $8$。

因此，找到牢房的最短时间为 8。