← 返回题目列表

Codeforces · 1667/F

F. 阴阳

中文机器翻译题面 查看原题

给您一个矩形网格,其中包含 $$$n$$$ 行和 $$$m$$$ 列。 $$$n$$$ 和 $$$m$$$ 可以被 $$$4$$$ 整除。有些细胞已经变成黑色或白色。保证没有两个彩色单元格共享一个角或边。

以黑色和白色单元格都正交连接或确定不可能的方式对剩余单元格进行着色。

考虑一个图,其中黑色单元格是节点。如果相应的单元共享一条边,则两个节点是相邻的。如果所描述的图形是连通的,则黑色单元格是正交连接的。白细胞也一样。

输入

输入由多个测试用例组成。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 4000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$8 \le n、m \le 500$$$、$$$n$$$ 和 $$$m$$$ 可被 $$$4$$$ 整除) — 行数和列数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符。每个字符是“B”、“W”或“.”,分别代表黑色、白色或空单元格。两种颜色(黑色或白色)的单元格不共享一个角或边缘。

保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$250\,000$$$。

输出

对于每个测试用例,如果没有解决方案,则打印“NO”,否则打印“YES”和具有相同格式的网格。如果有多个解决方案,您可以打印任何一个。

示例

输入 #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

注意

测试用例1的解决方案:

测试用例2:可以看到黑色和白色部分不能同时连接。所以答案是“不”。