AT_abc348_d [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$，他想移动到终点。请判断是否可能。

输入按以下格式从标准输入给出。 > $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 \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$ ## 样例解释 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)$ 也有药品，但如果使用它则无法到达终点。 ## 样例解释 2 高桥君无法从起点移动。 由 ChatGPT 4.1 翻译