2665 - 推箱子

「推箱子」是一款风靡全球的益智小游戏,玩家需要将箱子推到仓库中的目标位置。

游戏地图用大小为 m x n 的网格 表示,其中每个元素可以是墙、地板或者是箱子。

现在你将作为玩家参与游戏,按规则将箱子 'B' 移动到目标位置 'T' :

玩家的起始位置用字符 'S' 表示,只要他在地板上,就可以在网格中向上、下、左、右四个方向移动。玩家的起始位置也是地板。
地板用字符 '.' 表示,意味着可以自由行走。
墙用字符 '#' 表示,意味着障碍物,不能通行。
箱子仅有一个,用字符 'B' 表示。相应地,网格上有一个目标位置 'T'。
玩家需要站在箱子旁边,然后沿着箱子的方向进行移动,此时箱子会被移动到相邻的地板单元格。记作一次「推动」。
玩家无法越过箱子。
返回将箱子推到目标位置的最小 推动 次数,如果无法做到,请输出 -1。

输入

第一行有两个数字m,n。表示地图为m行n列。

第二行开始到m+1行,每一行有n个字符,为'#','.','S','B','T'的其中一种,意义见题目描述。另外保证题目的最外层字符必定是'#'

输出

只有一个数字箱子推到目标位置的最小 推动 次数,如果无法做到,请输出 -1。

样例

输入

6 6
######
#T####
#..B.#
#.##.#
#...S#
######

输出

3

提示

样例对应的图解释: 5 \leq n,m \leq 30

保证最外层都是#,保证每个测试数据'S','B','T'均出现一次

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题