分数: 425 点
问题陈述
有一个网格 H 行和 W 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。每个单元格的状态由字符表示 A_{i,j},其含义如下:
.:空单元格。#:一个障碍。S:空单元格和起点。T:空单元格和目标点。
高桥可以通过消耗从当前单元格移动到垂直或水平相邻的空单元格 1 能源。如果他的能量不足,他就无法移动 0,他也无法退出网格。
有 N 药品在格子里。的 i第一种药物在空单元格中 (R_i, C_i) 并可用于 设置 能量 to E_i。请注意,能量不一定会增加。他可以在当前的牢房中使用药物。用过的药就会消失。
高桥从起点开始 0 精力充沛,想要达到目标点。确定这是否可行。
约束
- 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
- (R_i, C_i) \neq (R_j, C_j) if i \neq j.
- A_{R_i, C_i} 不是
#. - 1 \leq E_i \leq HW
输入
输入由标准输入按以下格式给出:
H W
A_{1, 1}A_{1, 2}\cdotsA_{1, W}
A_{2, 1}A_{2, 2}\cdotsA_{2, W}
\vdots
A_{H, 1}A_{H, 2}\cdotsA_{H, W}
N
R_1 C_1 E_1
R_2 C_2 E_2
\vdots
R_N C_N E_N
输出
如果Takahashi可以从起点到达目标点,则打印 Yes;否则,打印 No.
示例输入 1
4 4 S... #..# #... ..#T 4 1 1 3 1 3 5 3 2 1 2 3 1
示例输出 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 2 S. T. 1 1 2 4
示例输出 2
No
高桥无法从起点移动。
示例输入 3
4 5 ..#.. .S##. .##T. ..... 3 3 1 5 1 2 3 2 2 1
示例输出 3
Yes