Medicines on Grid

题目描述

有一个有 $H$ 行 $W$ 列的格子。记位于从上数第 $i$ 行从左数第 $j$ 列的格子为 $(i, j)$。每个格子的状态由字符 $A_{i,j}$ 表示，含义如下：

$.$：空格子。 #：障碍物。 $S$：空格子且为起点。 $T$：空格子且为终点。

Takahashi 可以通过消耗 $1$ 点能量从当前格子移动到上下左右相邻的空格子。当能量为 $0$ 时无法移动，也不能走出网格。 网格中有 $N$ 个药物。第 $i$ 个药物位于空格子 $(R_i, C_i)$，可以被用来将能量设为 $E_i$。注意能量不一定会增加。他可以在自己所在的格子使用药物。使用过的药物会消失。 Takahashi 从起点以 $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$

输出格式

如果 Takahashi 能从起点到达终点，输出 $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$ 在 $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$。能量变为 $3$。 移动到 $(1, 2)$。能量变为 $2$。 移动到 $(1, 3)$。能量变为 $1$。 使用药物 $2$。能量变为 $5$。 移动到 $(2, 3)$。能量变为 $4$。 移动到 $(3, 3)$。能量变为 $3$。 移动到 $(3, 4)$。能量变为 $2$。 移动到 $(4, 4)$。能量变为 $1$。

途中在 $(2, 3)$ 处也有药物，但使用它会阻止他到达终点。
Takahashi 无法从起点移动。

标签: AtCoder|abc348D

来源

AtCoder|abc348D