[ABC348D] Medicines on Grid

### 问题描述 有一个$H$ 行和 $W$ 列的网格。 $(i, j)$ 表示位于从上往下第 $i$ 行和从左往右第 $j$ 列的单元格。每个单元格有字符 $A_{i,j}$ ： - `.`:空单元格。 - `#`:一个障碍物。 - `S`:空单元格和起点。 - `T`:空单元格和目标点。 高桥可以通过消耗 $1$ 能量从当前单元格移动到上下左右的空单元格。如果能量为 $0$ ，他就无法移动，也无法离开网格。 网格中有 $N$ 种药。 第$i$种药位于空格 $(R_i, C_i)$ 处，可以用来把能量 ***变成*** $E_i$ 。注意，能量并不一定会增加。他可以在当前格子中使用药物。使用过的药物会消失。 高桥以 $0$ 的能量从起点开始，并希望达到目标点。请判断这是否可行。 ### 数据与约定 - $1 \leq H, W \leq 200$ - $A_{i, j}$ 是 `.`、 `#`、 `S` 和 `T` 中的一个。 - `S` 和 `T` 都恰好存在一次。 - $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$

[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` を出力せよ。

4 4
S...
#..#
#...
..#T
4
1 1 3
1 3 5
3 2 1
2 3 1

Yes

2 2
S.
T.
1
1 2 4

No

4 5
..#..
.S##.
.##T.
.....
3
3 1 5
1 2 3
2 2 1

Yes

### 制約 - $ 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 高橋君はスタート地点から移動することができません。