1547 . Piece it together
Description
Tom has developed a special kind of puzzle: it involves a whole bunch of identical puzzle
pieces. The pieces have the shape of three adjoint squares in an L-shape. The corner square is
black, the two adjacent squares are white.
The puzzler is given a pattern of black and white squares in a rectangular grid. The challenge is to create that pattern using these pieces. The pieces can be rotated, but must not
overlap.
Tom has already designed a few nice patterns, but he needs to find out if they can be
constructed with the pieces at all. Rather than trying to test this for each pattern by hand, he
wants to write a computer program to determine this for him. Can you help him?
Input Format
On the first line a positive integer: the number of test cases, at most 100. After that per test
case:
1. one line with two integers n and m (1 ≤ n,m ≤ 500): the height and width of the grid
containing the pattern, respectively.
2. n lines, each containing m characters, denoting the grid. Each character is ‘B’, ‘W’, or ‘.’,
indicating a black, white or empty square respectively.
The grid contains at least one black or white square.
Output Format
Per test case:
one line with either “YES” or “NO”, indicating whether or not it is possible to construct
the pattern with the puzzle pieces. You may assume that there is an infinite supply of
pieces.
Sample Input 1
2 3 4 BWW. WWBW ..WB 3 3 W.. BW. WBW
Sample Output 1
YES NO
Hints
Problem Source
Migrated from old NTUJ.
NWERC2011
Subtasks
| No. | Testdata Range | Score |
|---|