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

输入 #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 之一。
• 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 翻译