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 翻译