0610 - うさぎちゃんとカメ

問題

縦幅 H × 横幅 W マスの 2 次元グリッドがあります。

うさぎちゃんは, 今いる地点からゴールへ目指して移動します。 ただしグリッド上にはカメが何匹か存在してうさぎちゃんを捕まえるために協力して最適に行動します。 カメとうさぎちゃんが同じマスに存在する時, うさぎちゃんは捕まります。

うさぎちゃんもカメも単位時間に, 現在のマスに留まるか, 隣接する上下左右のいずれかのマスに移動する行動ができます。 また壁やグリッドの外に移動することは出来ません。

このとき, うさぎちゃんはカメに捕まらずにゴールに着くことが出来るでしょうか。 うさぎちゃんとカメが同時にゴールに到着すると, うさぎちゃんは捕まえられることに注意してください。

入力

H W
S1,1 S1,2 ... S1,W
S2,1 S2,2 ... S2,W
:
SH,1 SH,2 ... SH,W

1 行目に縦幅 H, 横幅 W(2 ≤ H, W ≤ 200) が与えられます。

2 行目から H 行にかけてグリッドの情報が与えられます。 このうち i 行目 j 列目はそのマスの状態で, 以下のいずれかの文字で表されます。

• '@': うさぎちゃんの初期位置(何もないマス)
• '%': ゴール
• '$': カメの初期位置(何もないマス)
• '#': 壁
• '.': 何もないマス

'@' と '%' はグリッドに必ずちょうど 1 回現れることが保証されます。 また, うさぎちゃんの初期位置からゴールへ経路があることが保証されます。

出力

うさぎちゃんがカメに捕まらずに移動する方法があるとき 'Yes', どのように移動しても捕まる可能性があるとき 'No' を出力してください。

入出力例

入力例 1

2 4
%.@$
..$$

出力例 1

Yes

入力例 2

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

出力例 2

Yes

入力例 3

2 3
%$@
###

出力例 3

No

入力例 4

2 2
@%
..

出力例 4

Yes