Submit | All submissions | Best solutions | Back to list |
MCIRCLE - Minion Circle |
El Macho's army of mutated minions is marching towards Gru, the army is standing in a rectangular formation measuring N×M. The spray of antidotes done by Gru has turned some of the minions back to normal, but now they are trapped within the army of mutated ones. Formally, a normal minion is "not trapped" if :
1) either he is on one of the edges of the rectangle
2) or one of his direct neighbors (directly in front/back of him, or left/right of him) is not trapped.
Any trapped minion will be killed by the mutated minions, which Gru cannot let happen. Gru will use his antidote ray to turn exactly one row and one column of the army to normal minions. If there are any normal minions in that row or column, they remain unaffected. Can Gru select a row and a column such that no normal minion remains trapped after the antidote ray?
INPUT:
First line contains T, number of test cases
Each test case starts with a line containing two space separated integers N and M.
N lines follow, each containing M characters. jth character of the ith line is "B" if the minion at ith row and jth column in the army is mutated, "W" otherwise.
OUTPUT:
Print "YES or "NO" (quotes for clarity) to indicate whether it is possible for Gru to save the trapped minions.
CONSTRAINTS:
1<=T<=10
1<=N,M<=1000
SAMPLE INPUT:
1
3 3
BBB
BWB
BBB
SAMPLE OUTPUT:
YES
EXPLANATION:
Any row and column pair selected by Gru guarantees that the trapped minion does not remain trapped.
Added by: | Piyush Kumar |
Date: | 2014-07-27 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |