You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ABC348D] Medicines on Grid

题目描述

本题完全捆绑测评，只有0分和100分。

有一个 $H$ 行和 $W$ 列的网格。 $(i,j)$ 表示位于从上往下第 $i$ 行和从左往右第 $j$ 列的单元格。每个单元格有字符 $A_{i,j}$：

.:空单元格。

#:一个障碍物。

S:起点。

T:目标点。

高桥可以通过消耗 $1$ 能量从当前单元格移动到上下左右的空单元格。如果能量为 $0$ ，他就无法移动，也无法离开网格。

网格中有 $N$ 种药。 第i种药位于空格 $(R_i,C_i)$ 处，可以用来把能量变成 $E_i$。注意，能量并不一定会增加。他可以在当前格子中使用药物，药物不能带走，使用过的药物会消失。

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

输入格式

第一行两个整数 $H,W$ ，接下来 $H$ 行每行一个长度为 $W$ 的字符串表示这个迷宫，接下来一行一个整数 $N$ ，接下来 $N$ 行每行三个整数 $R_i,C_i,E_i$。

输出格式

如果可以到达终点输出 Yes ，否则输出 No 。

输入输出样例 #1

输入 #1

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

输出 #1

Yes

输入输出样例 #2

输入 #2

2 2
S.
T.
1
1 2 4

输出 #2

No

输入输出样例 #3

输入 #3

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

输出 #3

Yes

说明/提示

数据范围

• $1\ \leq\ H,\ W\ \leq\ 200$
• $A_{i,\ j}$ 只能是 ., #, 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$