← 返回题目列表

AtCoder · icpc2016autumn_b

B. 帮助公主!

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

问题陈述

某个王国的人民发起革命,反对公主的恶政。革命军入侵了公主居住的皇宫。军队的士兵正在探索宫殿以抓捕公主。你的工作是编写一个程序来决定公主是否可以逃离皇宫。

为了简单起见,宫殿的地面是一个划分为网格的矩形。网格中有两种单元格:一种是士兵和公主可以进入的单元格,另一种是士兵或公主不能进入的单元格。我们称前者为空牢房,后者为墙。公主和士兵一开始就在不同的空牢房里。网格中只有一个逃生舱口。如果公主到达舱口,那么公主就可以逃离宫殿。皇宫里的士兵大于等于零。

公主和所有士兵在每个单位时间内同时采取行动。换句话说,公主和士兵必须在不知道其他人下一步行动的情况下决定自己的行动。在每个单位时间内,公主和士兵可以移动到水平或垂直相邻的单元格,或者停留在当前单元格。而且公主和士兵不能离开宫殿的地面。如果公主和一名或多名士兵在移动后存在于同一个牢房中,那么公主就会被抓住。如果所有士兵都被移出宫殿,公主就可以保证只通过空牢房到达逃生舱口。

如果公主有一条路线,即使士兵有任何动作,士兵也无法抓住公主,那么公主就可以逃脱士兵的追捕。请注意,如果公主和士兵同时到达逃生口,公主就会被抓住。公主能逃出皇宫吗?


输入

每个数据集的格式如下。

$H$ $W$
$map_1$
:
:
$map_H$

数据集的第一行包含两个由空格分隔的正整数 $H$ 和 $W$,其中 $H$ 是网格的高度,$W$ 是网格的宽度。 ($2 \le H, W \le 200$)

后续$H$行中的第$i$行给出了字符串$map_i$,它表示宫殿地面的情况。

$map_i$是长度为$W$的字符串,$map_i$的第$j$个字符代表第$i$行第$j$列的单元格的状态。

'@'、'\$'、'%'、'.' 和 '#' 分别代表公主、士兵、逃生舱口、空牢房和墙壁。保证网格中仅存在1个'@'、仅存在1个'%'、大于等于0个'\$'。

输出

输出包含单词“的行Yes”,如果公主能逃出皇宫。否则,输出“No".



示例输入 1

2 4
%.@$
..$$

样本输入 1 的输出

Yes

示例输入 2

3 4
.%..
.##.
.@$.

样本输入 2 的输出

Yes

示例输入 3

2 3
%$@
###

样本输入 3 的输出

No

示例输入 4

2 3
@#$
.%.

样本输入 4 的输出

No

示例输入 5

2 2
@%
..

样本输入 5 的输出

Yes