最高分数: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} =
.
子任务
这个问题被分成几个子任务,如果你的程序打印出准备好的子任务的所有测试用例的正确答案,你将获得子任务的分数。
程序的分数是正确答案的子任务分数的总和。
- (60分): H = 1
- (130分): H = 2
- (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
:(