同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21845_Pieceittogether

2022-5-16 18:20| 发布者: Hocassian| 查看: 21| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505897062900-Problem List-采集的数据-后羿采集器.html

Pro.ID

21845

Title

Piece it together

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21845

AC

Submit

Ratio

66.67%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

描述

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?

输入

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

one line with two integers n and m ( 1 ≤ n, m ≤ 500 ): the height and width of the grid containing the pattern, respectively.
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.

输出

Description

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.

Input

On the first line a positive integer: the number of test cases, at most 100. After that per test case:

one line with two integers n and m ( 1 ≤ n, m ≤ 500 ): the height and width of the grid containing the pattern, respectively.
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

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

2
3 4
BWW.
WWBW
..WB
3 3
W..
BW.
WBW

Sample Output

YES
NO

Source

NWERC 2011