问题描述

在一个神秘的数字世界中，光头熊需要通过一个由 H 行和 W 列组成的网格迷宫。每个单元格用字符 $A_{i,j}$ 表示：

光头熊需要从起点 S 出发，到达终点 T。他们可以通过消耗能量来在空地上移动。初始时，他的能量值为 0。

在迷宫中，还有 N 个神秘能量源。每个能量源位于一个空地上，可以为光头熊提供新的能量值 Ei​。每个能量源只能被吸收一次，并且只有光头熊走到才能吸收。如果能量为 $0$ ，光头熊就无法移动，也无法离开网格。

光头熊希望以 $0$ 的能量从起点开始，并希望达到目标点。请判断这是否可行。

• .:空单元格。可以通过
• #:一个障碍物。不能通过
• S:空单元格和起点。
• T:空单元格和目标点。

输入格式

第一行为两个数 $H,W$。

接下来是一个 $H$ 行和 $W$ 列的网格。

再接下来是一个数 $N$。

最后 $N$ 行表示这 $N$ 个神奇能量，每一行描述其中一种，参数分别是 $R_i, C_i,E_i$，分别代表行坐标，纵坐标，能量值。

输出格式

如果可行，输出 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 都恰好存在一次。
• $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$