分数: 800 点
问题陈述
有一个长方形的池塘。 池塘被分成网格, H 行和 W 方格列。 我们将把正方形表示为 i从顶部开始的第行和 j从左起第 列 (i,\ j).
池塘中的一些方块包含漂浮在水面上的荷叶。 在其中一片叶子上, S,有一只青蛙试图到达另一片叶子 T。 正方形的状态 (i,\ j) 是由角色给你的 a_{ij},如下:
.:没有叶子的正方形。o:一个正方形,有一片叶子漂浮在水面上。S:带有叶子的正方形 S.T:带有叶子的正方形 T.
青蛙会重复执行以下动作来到达叶子 T: “跳转到与青蛙当前所在的叶子位于同一行或同一列的叶子。”
Snuke 正在尝试移除一些叶子,除了 S 和 T,这样青蛙就无法到达叶子 T。 确定这个目标是否可以实现。如果可以实现,找出需要移除的最少叶子数量。
约束
- 2 ≤ H, W ≤ 100
- a_{ij} is
.,o,SorT. - 正好有一个
S其中 a_{ij}. - 正好有一个
T其中 a_{ij}.
输入
输入由标准输入按以下格式给出:
H W
a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}
输出
如果目标可以实现,请打印需要移除的最少叶子数量。
否则,打印 -1 。
示例输入 1
3 3 S.o .o. o.T
示例输出 1
2
取下右上角和左下角的叶子。
示例输入 2
3 4 S... .oo. ...T
示例输出 2
0
示例输入 3
4 3 .S. .o. .o. .T.
示例输出 3
-1
示例输入 4
10 10 .o...o..o. ....o..... ....oo.oo. ..oooo..o. ....oo.... ..o..o.... o..o....So o....T.... ....o..... ........oo
示例输出 4
5