问题 23754 --古希腊之争(二)

23754: 古希腊之争(二)

时间限制: 1 Sec  内存限制: 128 MB
提交: 35  解决: 14
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][20kb]

题目描述

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

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

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

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

输入

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

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

输出

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

样例输入

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

样例输出

8

提示

来源

[提交][状态]