← 返回题目列表

AtCoder · s8pc_6_c

C. 无限网格

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

最高分数:400 点

问题陈述

我们有一个 H \times W 网格,其方块被涂成黑色或白色。
广场 i从顶部开始的第行和 j从左边算起的第列表示为单元格 (i, j).
细胞 (i, j) 被漆成黑色,如果 c_{i,j} = #和单元格 (i, j) 被漆成白色,如果 c_{i,j} = ..

下图是网格的示例, H = 5, W = 5.

让我们考虑一下连接 1 \ 000 \ 000 \ 000 相同 H \times W 网格如下:

连接后,网格大小为 H \times \left(10^9 \times W\right)。 Mr.square1001想要离开牢房 (1, 1) 到单元格 (H, 10^9 \times W)。在每次移动中,他只能移动到单元格 (i + 1, j) 或单元格 (i, j + 1) 来自单元格 (i, j)。另外,他只能传递一个白细胞。
是否可以从左上角单元格移动到右下角单元格?

约束

  • H, W 是介于 1 和 100 (含)
  • c_{i, j} is # or .
  • c_{1, 1} = .
  • c_{H, W} = .

子任务

这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。

  1. (60分): H = 1
  2. (130分): H = 2
  3. (210分):没有额外的限制。

输入

输入由标准输入按以下格式给出:

H W
c_{1, 1}c_{1, 2}c_{1, 3}...c_{1, W}
c_{2, 1}c_{2, 2}c_{2, 3}...c_{2, W}
c_{3, 1}c_{3, 2}c_{3, 3}...c_{3, W}
...
c_{H, 1}c_{H, 2}c_{H, 3}...c_{H, W}

输出

打印 Yay! 如果Mr.square1001可以从单元格中移动 (1, 1) 到单元格 (1000000000H, W)。否则,打印 :(.


示例输入 1

1 3
...

示例输出 1

Yay!

网格状态及移动示例如下。


示例输入 2

1 3
.#.

示例输出 2

:(

这种情况下是没有办法移动的。即使他也无法离开牢房 (1, 1) to (1, 3).


示例输入 3

3 3
.##
...
##.

示例输出 3

Yay!

网格状态及移动示例如下。


示例输入 4

7 7
..###..
...#...
#.....#
##.#.##
#.....#
...#...
..###..

示例输出 4

:(