← 返回题目列表

AtCoder · nadafes2022_day1_c

C. 洪水

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

配点 : 400 点

問題文

金枪鱼制作了一款游戏作为学园祭的展览品。

在那场比赛中 使用 H \times W 网格地牢。从上面 左起第 i\ (1 \leq i \leq H) 左起第 th 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) 方格并且此时岩浆没有侵蚀玩家的方格,游戏就会通关。

金枪鱼想看看是否可以通关这个游戏,但由于他正忙着准备学园祭,所以他请求你这位程序员帮助他。请判断这个游戏是否可以通关。

制約

  • 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

可以通过如下操作来通关游戏。 (黑色是墙壁,红色是岩浆)

flood_sample


入力例 2

4 4 2
...@
.#.#
....
@##.

出力例 2

No

无论你如何进行,你最终都会进入一个有岩浆的正方形。


入力例 3

4 4 2
.#.#
....
###.
@...

出力例 3

No

在这种情况下,玩家 当你到达 (H, W) 广场的那一刻,岩浆 (H, W) 将被侵蚀,导致游戏结束。


入力例 4

4 4 2
....
#...
@#.#
..#.

出力例 4

No

玩家是 我无法到达 (H, W) 并且无法完成游戏。