题目描述

長方形の池があります。 池は縦 $H$ 行、横 $W$ 列のマス目状に分割されています。 上から $i$ 行目、左から $j$ 列目のマスを $(i,\ j)$ と表します。

池のいくつかのマスには蓮 (はす) の葉が浮かんでいます。 ある葉 $S$ にはカエルが乗っており、別の葉 $T$ まで移動しようとしています。 マス $(i,\ j)$ の情報は、文字 $a_{ij}$ によって次のように表されます。

• . : 葉が浮かんでいないマスである。
• o : 葉が浮かんでいるマスである。
• S : 葉 $S$ が浮かんでいるマスである。
• T : 葉 $T$ が浮かんでいるマスである。

カエルは「今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプする」ことを繰り返し行い、葉 $T$ まで移動しようとしています。

すぬけ君の目標は、あらかじめ葉 $S$, $T$ 以外の葉を何枚か取り除いておくことで、カエルが葉 $T$ まで移動できないようにすることです。 この目標が達成可能か判定し、可能ならば取り除く葉の枚数の最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $a_{11}$ $...$ $a_{1W}$ $:$ $a_{H1}$ $...$ $a_{HW}$

输出格式

目標が達成可能ならば、取り除く葉の枚数の最小値を出力せよ。 そうでなければ、代わりに -1 を出力せよ。

题目大意

题目大意：

给定一个$H×W$的网格图，o是可以踩踏的点，.是不可踩踏的点。

现有一人在S处，向T移动，若此人现在在$(i,j)$上，那么下一步他可以移动到$(i,k),(k\in[1,W])$或$(k,j),(k\in[1,H])$上。

问最少需要将多少个o改成.，可以使这个人无法从S到达T，输出最少需要更改的数目；如果无论如何都不能使这个人无法从S到T，则输出-1

3 3
S.o
.o.
o.T

2

3 4
S...
.oo.
...T

0

4 3
.S.
.o.
.o.
.T.

-1

10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo

5

提示

制約

• $2\ <\ =\ H,\ W\ <\ =\ 100$
• $a_{ij}$ は ., o, S, T のどれかである。
• $a_{ij}$ のうち S はちょうど $1$ 個存在する。
• $a_{ij}$ のうち T はちょうど $1$ 個存在する。

Sample Explanation 1

右上と左下の葉を取り除けばよいです。