1048: 推箱子前传

Memory Limit：128 MB Time Limit：1.000 S Judge Style：Text Compare Creator：
Submit：80 Solved：24

Description

想象一下，你站在一个由方格组成的二维迷宫里，这些格子可能被填满岩石，也可能没被填满岩石。


你可以一步一个格子地往北、往南、往东或往西移动。这样的动作叫作“走”。其中一个空单元格包含一个箱子，你可以站在箱子旁边，推动箱子到相邻的自由单元格。这样的动作叫作“推”。箱子除了用推的方式，不能移动，如果你把它推到角落里，就再也不能把它从角落里拿出来了。将其中一个空单元格标记为目标单元格。你的工作是通过一系列走和推把箱子带到目标格子里。由于箱子很重，所以要尽量减少推的次数。

在推箱子的过程中，有时候需要换个方向进行。例如，先把箱子往右推了，然后需要把箱子往上推。这个时候需要人换在另外一个格子中站立。
然而，众所周知，人是一个很懒的生物，你希望在最短的距离内完成换位子的操作。

人不能走放置岩石和箱子的位置。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

第1行都包含两个整数r 和c （均小于或等于20），表示迷宫的行数和列数。接下来是r行，每行都包含c 个字符，每个字符都描述迷宫中的一个格子，对被填满岩石的格子用“#”表示，对空格用“.”表示。箱子的位置用“B”表示。“S”表示你所在的位置（初始位置），“T”表示你将要去的地方（终点）。

Output


一个整数，表示从初始位置到终点需要的最短步数（从S到T的最短步数），如果不能到达则输出-1

Sample Input Copy 

7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########

Sample Output Copy 

9

Source/Category