← 返回题单
题单练习 广度优先搜索
← 上一题 下一题 →

A5402 | Medicines on Grid

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有一个 $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
4 4
S...
#..#
#...
..#T
4
1 1 3
1 3 5
3 2 1
2 3 1
输出 #1
Yes
输入 #2
2 2
S.
T.
1
1 2 4
输出 #2
No
C++ 编辑器
输入
输出