#7714. 【入门】古希腊之争(二) 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述


话说,年轻的斯巴达勇士们终于走出迷宫,取得胜利并顺利赶了回来。可是等他们回到斯巴达的时候才发现,雅典人趁他们不在偷袭了城邦,并抓走了他们的臣民。侥幸逃出来的几个人说,他们被关押在一个迷宫的牢房里,并把关押他们的迷宫里的情况告诉了年轻的勇士:迷宫中的”S”点表示迷宫的入口,”T”点表示迷宫中牢房的位置,”.”表示空地,可以通过,”#”表示墙,不能直接通过,”K”表示陷阱,一旦进入就必死无疑。每次只能向上下左右四个方向移动,每移动一个单位距离需要耗费一个单位时间,所有斯巴达勇士的移动速度相同。
又是迷宫!!!这次斯巴达的勇士们彻底愤怒了!What’s more, today is the Magpie Festival!
由于斯巴达的勇士们无比愤怒,而且他们也想尽可能的在今天就能救出他们的臣民。所以当他们在迷宫中遇到墙的阻碍时,也能破墙进入。不过破墙的过程会花费一个单位的时间。现在请你计算一下他们最短需要多少时间才能找到迷宫的牢房。
PS:假设迷宫中每个点可以容纳的人数没有限制,所有勇士都是一起行动的,他们每次会一起向同一个方向移动。

输入格式

测试数据第一行输入二个数n,m(2=<m<=n<=20)分别代表迷宫的行数和列数。
下面n行每行有m个字符用来表示迷宫地图。

输出格式

输出一个整数,表示找到迷宫出口的最短时间,如不能找到出口输入-1。

样例

样例输入1

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

样例输出1

8