AT_arc074_d [ARC074F] Lotus Leaves

有一个长方形的池塘。池塘被分割为高 $H$ 行、宽 $W$ 列的网格。从上往下第 $i$ 行，从左往右第 $j$ 列的格子可以表示为 $(i,\, j)$。 池塘中的某些格子上漂浮着莲叶。某只青蛙正站在编号为 $S$ 的叶子上，准备移动到另一个编号为 $T$ 的叶子。每个格子 $(i,\, j)$ 的信息由字符 $a_{ij}$ 表示： - `.` ：该格子上没有莲叶。 - `o` ：该格子上有一片莲叶。 - `S` ：该格子上有编号为 $S$ 的莲叶。 - `T` ：该格子上有编号为 $T$ 的莲叶。 青蛙可以不断进行如下操作：“跳到当前所在叶子同一行或同一列上漂浮的另一个叶子上”。青蛙希望移动到叶 $T$。 すぬけ君的目标是，提前移除若干（可以为零）片叶子（不能移除 $S$ 和 $T$），使得青蛙无法从 $S$ 移动到 $T$。请判断能否实现该目标。如果可以，请输出最少需要移除的叶子数量。如果不能实现，请输出 $-1$。

输入为如下格式，从标准输入读入。 > $H$ $W$ > $a_{11} a_{12} ... a_{1W}$ > $\vdots$ > $a_{H1} a_{H2} ... a_{HW}$

如果目标可以实现，输出最少需要移除的叶子的数量。否则，请输出 $-1$。

### 限制 - $2 \leq H, W \leq 100$ - $a_{ij}$ 只会是 `.`, `o`, `S`, `T` 之一。 - 所有 $a_{ij}$ 中恰好有一个 `S`。 - 所有 $a_{ij}$ 中恰好有一个 `T`。 ### 样例解释 1 只需移除右上和左下的两片叶子即可。 由 ChatGPT 5 翻译