2015
05-23

# Brute Force?

Brute force may refer to any of several problem-solving methods involving the evaluation of multiple (or every) possible answer(s) for fitness. There is a very familiar brute-force problem for you.
There is an N * M grid, some are black while some are white. As iSea loves white more than black, he tries to change the color of all grids into white. Each time, he can choose one grid, and then the grid and its four adjacent grids will flip its color, that is, white to black, or black to white.
To make things worse, some grids are broken, and iSea can’t change color on this grid, but he can change its color with its unbroken adjacent grids. Is this task possible for him?

The first line contains a single integer T, indicating the number of test cases.
Each test case includes three integers N, M, K, K means the number of broken grids. Then N lines following, each line contains a string only contains ‘B’ or ‘W’, ‘B’ indicates black grid, ‘W’ indicates white grid.
Then K lines following, each line contains two integers Xi, Yi (1-based), means grid (Xi, Yi) is broken.

Technical Specification
1. 1 <= T <= 64
2. 1 <= N, M, K <= 256
3. 1 <= Xi <= N, 1 <= Yi <= M, no grid appears more than once.

The first line contains a single integer T, indicating the number of test cases.
Each test case includes three integers N, M, K, K means the number of broken grids. Then N lines following, each line contains a string only contains ‘B’ or ‘W’, ‘B’ indicates black grid, ‘W’ indicates white grid.
Then K lines following, each line contains two integers Xi, Yi (1-based), means grid (Xi, Yi) is broken.

Technical Specification
1. 1 <= T <= 64
2. 1 <= N, M, K <= 256
3. 1 <= Xi <= N, 1 <= Yi <= M, no grid appears more than once.

3
2 2 0
BW
BB
2 2 1
BW
BW
2 1
4 3 2
WBW
BBB
WBW
WWW
2 2
3 2

Case 1: Yes
Case 2: Yes
Case 3: No