← 返回题目列表

AtCoder · arc074_d

F. 荷叶

中文机器翻译题面 查看原题

分数: 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, S or T.
  • 正好有一个 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