Yin Yang

题意翻译

给你一个 $n$ 行 $m$ 列($4 \le$ $n$,$m$ $\le 500$)的方格图，保证 $n$,$m$ 能被 $4$ 整除。 现一些单元格是黑色或白色，给剩下单元格染上黑或白色，问有没有一种方案，让所用黑色和白色单元格都分别联通。若有输出"YES"并输出任意一种方案，否则输出"NO"，输出不含双引号。 联通指有公共边。 包含多组数据。组数 $\le 4,000$，保证在所有测试样例中 $n \times m$ 的和不超过 $250,000$。

题目描述

You are given a rectangular grid with $ n $ rows and $ m $ columns. $ n $ and $ m $ are divisible by $ 4 $ . Some of the cells are already colored black or white. It is guaranteed that no two colored cells share a corner or an edge. Color the remaining cells in a way that both the black and the white cells becomes orthogonally connected or determine that it is impossible. Consider a graph, where the black cells are the nodes. Two nodes are adjacent if the corresponding cells share an edge. If the described graph is connected, the black cells are orthogonally connected. Same for white cells.

输入输出格式

输入格式

The input consists of multiple test cases. The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 4000 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains two integers $ n $ , $ m $ ( $ 8 \le n, m \le 500 $ , $ n $ and $ m $ are divisible by $ 4 $ ) — the number of rows and columns. Each of the next $ n $ lines contains $ m $ characters. Each character is either 'B', 'W' or '.', representing black, white or empty cell respectively. Two colored (black or white) cell does not share a corner or an edge. It is guaranteed that the sum of $ n \cdot m $ over all test cases does not exceed $ 250\,000 $ .

输出格式

For each testcase print "NO" if there is no solution, otherwise print "YES" and a grid with the same format. If there are multiple solutions, you can print any.

输入输出样例

输入样例 #1

4
8 8
.W.W....
.....B.W
.W.W....
.....W.W
B.B.....
....B.B.
B.W.....
....B.B.
8 8
B.W..B.W
........
W.B..W.B
........
........
B.W..B.W
........
W.B..W.B
8 12
W.B.........
....B...B.W.
B.B.........
....B...B.B.
.B..........
........B...
.W..B.B...W.
............
16 16
.W............W.
...W..W..W.W....
.B...........B.W
....W....W......
W......B....W.W.
..W.......B.....
....W...W....B.W
.W....W....W....
...B...........W
W.....W...W..B..
..W.W...W......B
............W...
.W.B...B.B....B.
.....W.....W....
..W......W...W..
W...W..W...W...W

输出样例 #1

YES
BWWWWWWW
BWBBBBBW
BWBWWWBW
BWBWBWBW
BWBWBWBW
BWBBBWBW
BWWWWWBW
BBBBBBBW
NO
YES
WWBBBBBBBBBB
BWWWBBBBBBWB
BBBWBBBWWWWB
BBBWBBBWBBBB
BBBWBBBWBBBB
BBBWWWWWBBBB
BWWWBBBWWWWB
BBBBBBBBBBBB
YES
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WBBBBBBBBBBBBBWW
WBBBWBWWWWBWWBWW
WBBWWBBBWWBWWBWW
WBWWWBWWWWBWWBWW
WBBWWBBBWWBWWBWW
WWBWWWWWWWWWWWWW
WWBBBBBBBBBBBBWW
WBBBWWWBWWWBWBWW
WWWBWBBBWBBBWBBB
WWWBWBWWWWWBWWBW
WWWBWBBBWBBBWWBW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW

说明

Solution for test case 1: Test case 2: one can see that the black and the white part can't be connected in the same time. So the answer is "NO".