话说，年轻的斯巴达勇士们终于走出迷宫，取得胜利并顺利赶了回来。可是等他们回到斯巴达的时候才发现，雅典人趁他们不在偷袭了城邦，并抓走了他们的臣民。

侥幸逃出来的几个人说，他们被关押在一个迷宫的牢房里，并把关押他们的迷宫里的情况告诉了年轻的勇士：迷宫中的S点表示迷宫的入口，T点表示迷宫中牢房的位置，.表示空地，可以通过，#表示墙，不能直接通过，K表示陷阱，一旦进入就必死无疑。

每次只能向上下左右四个方向移动，每移动一个单位距离需要耗费一个单位时间，所有斯巴达勇士的移动速度相同。

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

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

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

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

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

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

深搜

深搜