/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
maguro君は文化祭の展示でとあるゲームを作りました。
そのゲームでは H \times W のグリッド型のダンジョンが使われます。上から i\ (1 \leq i \leq H) 番目、左から j\ (1 \leq j \leq W) 番目のマスを (i,j) とします。
(i,j) のスタート時の状態は、A_{i,j} が . のとき道、# のとき壁、@ のときマグマです。
プレイヤーは最初 (1, 1) にいて、スタートから 1 秒ごとに上下左右に隣接する道のマスに 1 マス動きます（ただし、ダンジョンの外は壁となっており進めません）。しかし、スタートしてから K, 2K, 3K \dots 秒経ったタイミングでマグマが上下左右に隣接する道のマスに浸食します。プレイヤーがマグマのあるマスに入るか、プレイヤーがいるマスにマグマが浸食するとゲームオーバーです。
なお、プレイヤーが (H, W) に到達した瞬間にプレイヤーのいるマスにマグマが浸食してもゲームオーバーとなります。
プレイヤーが (H,W) のマスに到達し、かつその瞬間にマグマがプレイヤーのいるマスに浸食しなかった場合、ゲームクリアとなります。
maguro君はこのゲームがクリア可能かどうかを確かめようとしましたが、文化祭の準備で忙しかったので、プログラマーであるあなたに頼んできました。このゲームがクリア可能か判定してください。
制約
- 2 \leq H \leq 2000
- 2 \leq W \leq 2000
- 1 \leq K \leq 2000
- A_{i,j} は
.,#,@のいずれか - A_{1,1} =
., A_{H,W} =. - H,W,K は整数
入力
入力は以下の形式で標準入力から与えられる。
H\ W\ K
A_{1, 1}A_{1, 2} \dots A_{1,W}
A_{2, 1}A_{2, 2} \dots A_{2, W}
\vdots
A_{H, 1}A_{H, 2} \dots A_{H, W}
出力
ゲームがクリア可能なら Yes、不可能なら No と出力せよ。
入力例 1
4 4 2 ..@# #.#. .... @##.
出力例 1
Yes
以下のように進むとゲームをクリアすることが可能です。（黒が壁、赤がマグマ）
入力例 2
4 4 2 ...@ .#.# .... @##.
出力例 2
No
どのように進んでも必ずマグマのあるマスに入ってしまいます。
入力例 3
4 4 2 .#.# .... ###. @...
出力例 3
No
この場合、プレイヤーが (H, W) のマスにたどり着いた瞬間にマグマが (H, W) に浸食するため、ゲームオーバーとなってしまいます。
入力例 4
4 4 2 .... #... @#.# ..#.
出力例 4
No
プレイヤーは (H, W) にたどり着くことができず、ゲームをクリアすることができません。