Problem 1075 --搜索-古希腊之争(二)

1075: 搜索-古希腊之争(二)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 29  Solved: 6
[Submit][Status][Web Board][Creator:]

Description

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

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

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

PS:假设迷宫中每个点可以容纳的人数没有限制,每个斯巴达勇士的行动方向之间没有影响。

Input

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

0 0表示输入结束,详细输入格式见样例。

Output

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

Sample Input

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

Sample Output

8

Source

[Submit][Status]