← 返回题目列表

AtCoder · abc348_d

G. 网格上的药品

中文机器翻译题面 查看原题

分数: 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