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

View as PDF

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 grid of squares. Each square has an integer coordinate with the lower left square having the coordinate , and the upper right square having the coordinate . 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 . 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 . Can you determine if the current grid is possible after exactly 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.

#### Input Specification

The first line contains a single integer .

The second line contains a single integer .

The following lines describe the current grid. Each line contains a string of characters consisting of only B and W. If the character of the lines is B, then the square with the coordinate is black. Otherwise, it is white.

#### Output Specification

Output YES if the given grid is possible after exactly 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 second, the given grid cannot be created from the initial grid, no matter what events happen during the first second.