恐怖机器人¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB
背景故事¶
未来科技正在测试一台没有远程武器的遥控战斗要塞。指挥官派出经过伪装的恐怖机器人，准备把它引进陷阱。机器人跑得不比要塞快，只有不断转向，才能在追逐中避免被撞毁。
侦察员标出了障碍、陷阱和原型机可能出现的位置。每次行动还可以炸掉一个完整的障碍。请为每个可能的起点判断行动结果。
形式化问题描述¶
地图有 \(n\) 行、\(m\) 列。字符 B 表示障碍格，T 表示陷阱格，S 表示待询问的要塞起点，E 表示普通空地。每次只放置一台要塞；其他 S 格也视为空地。
上下左右相邻的障碍格属于同一个障碍连通块。一次行动可以在开始前炸掉至多一个这样的连通块，其所有格子变为空地。各个起点的行动彼此独立，可以选择不同的轰炸目标。
要塞和机器人都在格子上活动。相邻指水平、竖直或对角相邻的八个格子；对角移动不受两侧格子阻挡，只要求目的格可通行。
图 1：相同字母表示同一个障碍连通块。图中不同字母的障碍块即使在角上相接，也不合并。蓝色箭头展示一段无需轰炸、且连续两步不共线的行进路线；圆圈数字表示先后位置，左侧和上方数字分别为行号与列号。
每个机器人可以空投到任意可通行且未被要塞占据的格子，包括陷阱格。空投不计时间。机器人进入要塞的相邻格后，按以下规则行动：
- 设要塞在 \(u\) ，机器人在相邻格 \(v\) .机器人可以停留在 \(v\) ，或者尝试移动到与 \(v\) 相邻的可通行格 \(w\) .
- 若机器人停留，或 \(u,v,w\) 共线，机器人在移动前被摧毁。判断共线时也包括 \(w=u\) .
- 否则，机器人成功移动到 \(w\) .无论机器人是否被摧毁，要塞都移动到机器人原来的位置 \(v\) ，计一次移动。
- 要塞一进入任意陷阱便被捕获，行动立即结束。最后一步允许牺牲机器人。若机器人被摧毁而要塞尚未被捕获，可以继续空投新的机器人。
要塞没有相邻机器人时保持不动。空投地点可以直接选在相邻格，因此不需要计算机器人单独接近要塞的时间。
对每个 S 格，在所有轰炸选择中：
- 若一个机器人能够完成捕获，求要塞的最少移动次数；
- 否则，若有限个机器人能够完成捕获，输出
-2； - 否则输出
-1.
下图展示要塞分别位于机器人正上方和左上方时，机器人一步内的安全去向。图示假设周围格子都可通行。
图 2：方框 F 表示要塞，圆圈 D 表示机器人。勾号格是安全去向；叉号表示机器人会被摧毁，包括原地停留、退向要塞或沿同一直线向前移动。红色虚线标出这条直线。蓝色箭头表示本步要塞都会进入机器人原来的格子。实际地图中还须排除越界和未炸除的障碍格。
输入格式¶
第一行包含两个整数 \(n,m\) .
接下来 \(n\) 行，每行一个长度为 \(m\) 的字符串，描述地图。
输出格式¶
按从上到下、每行从左到右的顺序，对每个 S 输出一行答案。
样例 1¶
输入¶
5 5
SBBEE
BEEEE
EBBEE
EEEBT
EEEEE
输出¶
5
解释¶
炸掉第一行第 \(2,3\) 列组成的障碍。要塞可依次经过 \((1,1),(1,2),(2,3),(2,4),(3,5),(4,5)\) .相邻两步都不共线，共移动 \(5\) 次；机器人最后停在陷阱上。
图 3：虚线斜纹区域 a 被整体炸除，其余三个障碍块 b 、c 、d 保留。机器人先空投到圆圈 \(1\) 所在格，之后依次向圆圈 \(2\) 到 \(5\) 移动，最后停在 T 上；要塞沿蓝色箭头从 S 经过五步进入陷阱。
样例 2¶
输入¶
1 4
STES
输出¶
1
-2
解释¶
左端起点与陷阱相邻，移动一次即可捕获。右端起点只能沿同一直线走两步，必须使用多个机器人。
样例 3¶
输入¶
1 5
SBBBT
输出¶
-2
解释¶
三个障碍格属于同一连通块，可以一起炸掉。直线路径需要多个机器人。
样例 4¶
输入¶
1 5
SBEBT
输出¶
-1
解释¶
两个障碍格属于不同连通块。只能炸掉一个，因此始终无法到达陷阱。
数据范围与保证¶
- \(1\le n,m\le40\) .
- 每格均为
B、S、T、E之一。 - 允许没有障碍、起点或陷阱。没有起点时不输出任何内容；没有陷阱时每个起点的答案均为
-1.
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 30% | \(n,m\le5\) |
| 10% | 恰有一个起点和一个陷阱 |
| 20% | 恰有一个陷阱 |
| 40% | 无额外条件 |