网格中的药品

题目描述

有一个 $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

例如,他可以按如下方式到达终点:

使用药品 $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 2
S.
T.
1
1 2 4

No

高桥君无法从起点移动。

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

Yes

数据范围

• $1 \le H, W \le 200$
• $A_{i,j}$ 是 .、#、S、T 之一。
• 在 $A_{i,j}$ 中,S 和 T 各恰好出现一次。
• $1 \le N \le 300$
• $1 \le R_i \le H$
• $1 \le C_i \le W$
• 若 $i \neq j$,则 $(R_i, C_i) \neq (R_j, C_j)$。
• $A_{R_i, C_i}$ 不是 #。
• $1 \le E_i \le HW$