Wesley's Anger Contest 3 Bonus Problem - Game of Death

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

The following problem was originally planned for problem 4 in Wesley's Anger Contest 3.

There is a (2N + 1) \times (2N + 1) grid of squares. Each square has an integer coordinate with the lower left square having the coordinate (-N, -N), and the upper right square having the coordinate (N, N). Each square is coloured either black or white.

Initially, the entire grid is white, except for a single black square in the center of the grid at (0, 0). For each second afterwards, any number of the following events can happen to any number of black squares currently on the grid:

  • any number of white squares that share a side with that black square can become black
  • the black square becomes white

It is possible that the grid remains unchanged between one second and the next, and it is possible that there are no black squares remaining.

You are given a grid of squares, the current colour of each square, as well as the current time T. Can you determine if the current grid is possible after exactly T seconds have elapsed?

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

0 \le T \le 10^9
0 \le N \le 500

Subtask 1 [10%]

N = 0

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line contains a single integer T.

The second line contains a single integer N.

The following 2N + 1 lines describe the current grid. Each line contains a string of 2N + 1 characters consisting of only B and W. If the x^{th} character of the y^{th} lines is B, then the square with the coordinate (x, y) is black. Otherwise, it is white.

Output Specification

Output YES if the given grid is possible after exactly T seconds have elapsed and NO otherwise.

Sample Input 1

1
0
B

Sample Output 1

YES

Sample Explanation 1

The given grid corresponds to the initial grid. Thus, we can create the given grid by having no events occur during the first second.

Sample Input 2

2
1
BWB
WWW
BWB

Sample Output 2

YES

Sample Explanation 2

Below is one possible way to create the current grid.

T=0      T=1      T=2

WWW      WBW      BWB
WBW  ->  BWB  ->  WWW
WWW      WWW      BWB

Sample Input 3

1
1
BWW
WBW
WWW

Sample Output 3

NO

Sample Explanation 3

After 1 second, the given grid cannot be created from the initial grid, no matter what events happen during the first second.


Comments

There are no comments at the moment.