[ABC348] D - Medicines on Grid

D - Medicines on Grid

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 425 分

题面

有一个 行 列的网格。用 表示从顶部第 行、从左侧第 列的单元格。每个单元格的状态用字符 表示，代表如下含义：

• .：空单元格。
• #：障碍物。
• S：空单元格，起始点。
• T：空单元格，目标点。

高桥可以消耗 点能量从当前单元格移动到垂直或水平相邻的空单元格。如果他的能量为 ，他将无法移动，也不能离开网格。

网格中有 个药物。第 个药物在空单元格 处，可以将能量 设置为 。注意能量不一定会增加。他可以在当前单元格使用药物。使用后药物会消失。

高桥从起始点开始，能量为 ，希望到达目标点。判断这是否可能。

限制条件

• 是 ., #, S, T 中的一种。
• S 和 T 在 中恰好各出现一次。
• 若 ，则 。
• 不是 #。

---

输入

输入从标准输入中按以下格式给出：

输出

如果高桥能够从起始点到达目标点，则输出 Yes；否则输出 No。

---

输入样例 1

4 4
S...
#..# <br#...
..#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

高桥无法从起始点移动。

---

输入样例 3

4 5
..#..
.S##. <br.##T.
.....
3
3 1 5
1 2 3
2 2 1

输出样例 3

Yes