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.
For all subtasks:
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
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.
Comments