C - Infinite Grid Editorial /

Time Limit: 1 sec / Memory Limit: 976 MB

配点：400 点

問題文

H * W のマス目があります。上から i 行目 (1 \leq i \leq H)、左から j 列目 (1 \leq j \leq W) にあるマスを、マス (i, j) と呼ぶことにします。
マス (i, j) は、c_{i, j} = # のとき黒で塗られており、c_{i, j} = . のとき白で塗られています。

下の図は、H = 5, W = 5 の場合のマス目の例です。

さて、このマス目を 1 \ 000 \ 000 \ 000 = 10^{9} 個横に繋げることを考えます。例えば、上の例のマス目を横に 10^{9} 個繋げると、以下のようになります。

square1001 君は、この広いマス目の中を、左上のマス (1, 1) から右下のマス (H, 10^9 \times W) まで移動します。ただし、以下の条件で移動する必要があります。

  • 黒いマスを通らずに移動しなければならない。
  • マス (i, j) からは、マス (i + 1, j) あるいはマス (i, j + 1) にしか移動することができない。
  • マス目の外に出るような移動は許されない。

彼が条件に従って移動できるかどうかを判定してください。

制約

  • H, W は 1 以上 100 以下の整数
  • c_{i, j} は # か . のどちらかである
  • 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}

出力

square1001 君が左上から右下のマスまで移動できる場合 Yay!、移動できない場合 :( と出力してください。

入力例 1

1 3
...

出力例 1

Yay!

マス目は次のようになっており、下図のように移動することで目標を達成することができます。

入力例 2

1 3
.#.

出力例 2

:(

この場合、どうやっても目標を達成できません。それどころか、(1, 3) にすらたどり着くことができません！

入力例 3

3 3
.##
...
##.

出力例 3

Yay!

下図のように移動すると目標を達成することができます。

入力例 4

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

出力例 4

:(

Max Score：400 points

Problem Statement

We have an H \times W grid whose squares are painted black or white.
The square at the i-th row from the top and the j-th column from the left is denoted as cell (i, j).
Cell (i, j) is painted black if c_{i,j} = #, and cell (i, j) is painted white if c_{i,j} = ..

Following picture is an example of grid which is H = 5, W = 5.

Let's think about connecting 1 \ 000 \ 000 \ 000 same H \times W grids like follows:

After connecting, the grid size will be H \times \left(10^9 \times W\right). Mr.square1001 wants to move from cell (1, 1) to cell (H, 10^9 \times W). In each moves, he can move only to cell (i + 1, j) or cell (i, j + 1) from cell (i, j). In addition, he can only pass on a white cell.
Is it possible to move from the top-left corner cell to the bottom-right corner cell?

Constraints

  • H, W is an integer between 1 and 100 (inclusive)
  • c_{i, j} is # or .
  • c_{1, 1} = .
  • c_{H, W} = .

Subtasks

This problem is separated several two subtasks, and you will get score of the subtask if your program prints the correct answer for all testcases for the subtask prepared.
The score for a program is the sum of score of subtasks of correct answer.

  1. (60 points) : H = 1
  2. (130 points) : H = 2
  3. (210 points) : No additional constraints.

Input

Input is given from Standard Input in the following format: 

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}

Output

Print Yay! if Mr.square1001 can move from cell (1, 1) to cell (1000000000H, W). Otherwise, print :(.

Sample Input 1

1 3
...

Sample Output 1

Yay!

The state of grid and an example of movement is as follows.

Sample Input 2

1 3
.#.

Sample Output 2

:(

In this case, there is no way to move. Even he cannot move from cell (1, 1) to (1, 3).

Sample Input 3

3 3
.##
...
##.

Sample Output 3

Yay!

The state of grid and an example of movement is as follows.

Sample Input 4

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

Sample Output 4

:(