#œ. 【入门】古希腊之争(二)

    Type: Default 1000ms 128MiB

【入门】古希腊之争(二)

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

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

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

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

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

输入格式

测试数据第一行输入二个数n,m(2=<m<=n<=20)分别代表迷宫的行数和列数。

下面n行每行有m个字符用来表示迷宫地图。

输出格式

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

样例

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

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45