AT_abc348_d [ABC348D] Medicines on Grid

[problemUrl]: https://atcoder.jp/contests/abc348/tasks/abc348_d $ H $ 行 $ W $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマス目を $ (i,\ j) $ と表します。各マスの状態は文字 $ A_{i,j} $ で表され、意味は以下の通りです。 - `.` : 空きマス。 - `#` : 障害物。 - `S` : 空きマスかつスタート地点。 - `T` : 空きマスかつゴール地点。 高橋君は、今いるマスから上下左右に隣り合う空きマスへ、エネルギーを $ 1 $ 消費して移動することができます。ただし、エネルギーが $ 0 $ の状態で移動することはできず、またグリッドの外へ移動することはできません。 グリッドには合計で $ N $ 個の薬があります。$ i $ 番目の薬は空きマス $ (R_i,\ C_i) $ にあり、使うとエネルギーを **$ E_i $ にする**ことができます。必ずしもエネルギーが増えるとは限らないことに注意してください。高橋君は自分のいるマスにある薬を使うことができます。使った薬はなくなります。 高橋君ははじめエネルギー $ 0 $ の状態でスタート地点にいて、ゴール地点まで移動したいです。これが可能かどうか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ A_{1,\ 1} $$ A_{1,\ 2} $$ \cdots $$ A_{1,\ W} $ $ A_{2,\ 1} $$ A_{2,\ 2} $$ \cdots $$ A_{2,\ W} $ $ \vdots $ $ A_{H,\ 1} $$ A_{H,\ 2} $$ \cdots $$ A_{H,\ W} $ $ N $ $ R_1 $ $ C_1 $ $ E_1 $ $ R_2 $ $ C_2 $ $ E_2 $ $ \vdots $ $ R_N $ $ C_N $ $ E_N $

高橋君がスタート地点からゴール地点へ移動することが可能なら `Yes` 、不可能なら `No` を出力せよ。

### 制約 - $ 1\ \leq\ H,\ W\ \leq\ 200 $ - $ A_{i,\ j} $ は `.`, `#`, `S`, `T` のいずれかである。 - `S` と `T` は $ A_{i,\ j} $ にそれぞれちょうど $ 1 $ つ存在する。 - $ 1\ \leq\ N\ \leq\ 300 $ - $ 1\ \leq\ R_i\ \leq\ H $ - $ 1\ \leq\ C_i\ \leq\ W $ - $ i\ \neq\ j $ ならば $ (R_i,\ C_i)\ \neq\ (R_j,\ C_j) $ - $ A_{R_i,\ C_i} $ は `#` でない。 - $ 1\ \leq\ E_i\ \leq\ HW $ ### Sample Explanation 1 例えば、以下のようにしてゴール地点へ移動することができます。 - 薬 $ 1 $ を使う。エネルギーが $ 3 $ になる。 - $ (1,\ 2) $ へ移動する。エネルギーが $ 2 $ になる。 - $ (1,\ 3) $ へ移動する。エネルギーが $ 1 $ になる。 - 薬 $ 2 $ を使う。エネルギーが $ 5 $ になる。 - $ (2,\ 3) $ へ移動する。エネルギーが $ 4 $ になる。 - $ (3,\ 3) $ へ移動する。エネルギーが $ 3 $ になる。 - $ (3,\ 4) $ へ移動する。エネルギーが $ 2 $ になる。 - $ (4,\ 4) $ へ移動する。エネルギーが $ 1 $ になる。 この移動の途中には $ (2,\ 3) $ にも薬がありますが、これを使うとゴールできません。 ### Sample Explanation 2 高橋君はスタート地点から移動することができません。