# 恐怖机器人

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB

## 背景故事

未来科技正在测试一台没有远程武器的遥控战斗要塞。指挥官派出经过伪装的恐怖机器人，准备把它引进陷阱。机器人跑得不比要塞快，只有不断转向，才能在追逐中避免被撞毁。

侦察员标出了障碍、陷阱和原型机可能出现的位置。每次行动还可以炸掉一个完整的障碍。请为每个可能的起点判断行动结果。

## 形式化问题描述

地图有 $n$ 行、$m$ 列。字符 `B` 表示障碍格，`T` 表示陷阱格，`S` 表示待询问的要塞起点，`E` 表示普通空地。每次只放置一台要塞；其他 `S` 格也视为空地。

上下左右相邻的障碍格属于同一个障碍连通块。一次行动可以在开始前炸掉至多一个这样的连通块，其所有格子变为空地。各个起点的行动彼此独立，可以选择不同的轰炸目标。

要塞和机器人都在格子上活动。相邻指水平、竖直或对角相邻的八个格子；对角移动不受两侧格子阻挡，只要求目的格可通行。

![三个四连通障碍块a、b、c及从角相接障碍之间通过的路线，圆圈0到7依次标出位置](assets/diagonal-passages.svg)

图 1：相同字母表示同一个障碍连通块。图中不同字母的障碍块即使在角上相接，也不合并。蓝色箭头展示一段无需轰炸、且连续两步不共线的行进路线；圆圈数字表示先后位置，左侧和上方数字分别为行号与列号。

每个机器人可以空投到任意可通行且未被要塞占据的格子，包括陷阱格。空投不计时间。机器人进入要塞的相邻格后，按以下规则行动：

1. 设要塞在 $u$ ，机器人在相邻格 $v$ .机器人可以停留在 $v$ ，或者尝试移动到与 $v$ 相邻的可通行格 $w$ .
2. 若机器人停留，或 $u,v,w$ 共线，机器人在移动前被摧毁。判断共线时也包括 $w=u$ .
3. 否则，机器人成功移动到 $w$ .无论机器人是否被摧毁，要塞都移动到机器人原来的位置 $v$ ，计一次移动。
4. 要塞一进入任意陷阱便被捕获，行动立即结束。最后一步允许牺牲机器人。若机器人被摧毁而要塞尚未被捕获，可以继续空投新的机器人。

要塞没有相邻机器人时保持不动。空投地点可以直接选在相邻格，因此不需要计算机器人单独接近要塞的时间。

对每个 `S` 格，在所有轰炸选择中：

- 若一个机器人能够完成捕获，求要塞的最少移动次数；
- 否则，若有限个机器人能够完成捕获，输出 `-2` ；
- 否则输出 `-1` .

下图展示要塞分别位于机器人正上方和左上方时，机器人一步内的安全去向。图示假设周围格子都可通行。

![左图要塞在机器人正上方，右图在左上方；勾号表示安全去向，同一直线上的叉号位置会导致机器人被摧毁](assets/movement.svg)

图 2：方框 `F` 表示要塞，圆圈 `D` 表示机器人。勾号格是安全去向；叉号表示机器人会被摧毁，包括原地停留、退向要塞或沿同一直线向前移动。红色虚线标出这条直线。蓝色箭头表示本步要塞都会进入机器人原来的格子。实际地图中还须排除越界和未炸除的障碍格。

## 输入格式

第一行包含两个整数 $n,m$ .

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，描述地图。

## 输出格式

按从上到下、每行从左到右的顺序，对每个 `S` 输出一行答案。

## 样例 1

### 输入

```text
5 5
SBBEE
BEEEE
EBBEE
EEEBT
EEEEE
```

### 输出

```text
5
```

### 解释

炸掉第一行第 $2,3$ 列组成的障碍。要塞可依次经过 $(1,1),(1,2),(2,3),(2,4),(3,5),(4,5)$ .相邻两步都不共线，共移动 $5$ 次；机器人最后停在陷阱上。

![样例1的五步捕获路线：先炸掉第一行相邻的两个障碍格a，要塞沿0到5进入陷阱T](assets/sample-route.svg)

图 3：虚线斜纹区域 `a` 被整体炸除，其余三个障碍块 `b` 、`c` 、`d` 保留。机器人先空投到圆圈 $1$ 所在格，之后依次向圆圈 $2$ 到 $5$ 移动，最后停在 `T` 上；要塞沿蓝色箭头从 `S` 经过五步进入陷阱。

## 样例 2

### 输入

```text
1 4
STES
```

### 输出

```text
1
-2
```

### 解释

左端起点与陷阱相邻，移动一次即可捕获。右端起点只能沿同一直线走两步，必须使用多个机器人。

## 样例 3

### 输入

```text
1 5
SBBBT
```

### 输出

```text
-2
```

### 解释

三个障碍格属于同一连通块，可以一起炸掉。直线路径需要多个机器人。

## 样例 4

### 输入

```text
1 5
SBEBT
```

### 输出

```text
-1
```

### 解释

两个障碍格属于不同连通块。只能炸掉一个，因此始终无法到达陷阱。


## 数据范围与保证

- $1\le n,m\le40$ .
- 每格均为 `B` 、`S` 、`T` 、`E` 之一。
- 允许没有障碍、起点或陷阱。没有起点时不输出任何内容；没有陷阱时每个起点的答案均为 `-1` .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 30% | $n,m\le5$ |
| 10% | 恰有一个起点和一个陷阱 |
| 20% | 恰有一个陷阱 |
| 40% | 无额外条件 |