题目描述

Prof. Shou is given an $n\times m$ board. Some cells are colored black, some cells are colored white, and others are uncolored.

Prof. Shou likes check patterns, so he wants to color all uncolored cells and maximizes the number of check patterns on the board.

$4$ cells forming a $2\times 2$ square are said to have the check pattern if they are colored in one of the following ways:

BW
WB

WB
BW

Here W ("wakuda" in Chewa language) means the cell is colored black and B ("biancu" in Corsican language) means the cell is colored white.

输入格式

The first line contains a single integer $T$ $(1\leq T \leq 10^4)$ denoting the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1\le n, m\le 100$) denoting the dimensions of the board.

Each of the next $n$ lines contains $m$ characters. The $j$-th character of the $i$-th line represents the status of the cell on the $i$-th row and $j$-th column of the board. The character is W if the cell is colored black, B if the cell is colored white, and ? if the cell is uncolored.

It is guaranteed that the sum of $nm$ over all test cases is no more than $10^6$.

输出格式

For each test case, output a line containing the maximum number of check patterns on the board.

In the next $n$ lines, output the colored board in the same format as the input. The output board should satisfy the following conditions.

• It consists of only B and W.
• If a cell is already colored in the input, its color cannot be changed in the output.
• The number of check patterns equals the answer you print.

If there are multiple solutions, output any of them.

题目大意

题目描述

教授 Shou 得到了一个 $(n \times m)$ 的棋盘。一些格子被涂成了黑色，一些被涂成了白色，还有一些没有上色。

教授 Shou 喜欢棋盘图案，所以他想给所有未上色的格子涂色，并最大化棋盘上的棋盘图案数量。

如果四个形成一个 $(2 \times 2)$ 方格的单元格以以下任一种方式上色，则说它们形成了一个棋盘图案：

BW

WB

或者

WB

BW

这里的 W（在奇瓦语中是“wakuda”，意为黑色）表示格子被涂成了黑色，而 B（在科西嘉语中是“biancu”，意为白色）表示格子被涂成了白色。

输入格式

第一行包含一个整数 $T (1 \leq T \leq 10^4)$，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 100)$，表示棋盘的尺寸。

接下来的 $n$ 行每行包含 $m$ 个字符。第 $i$ 行的第 $j$ 个字符表示棋盘上第 $i$ 行和第 $j$ 列的格子的状态。如果格子被涂成了黑色，则字符为 W；如果格子被涂成了白色，则字符为 B；如果格子未上色，则字符为 ?。

保证所有测试用例中 $n \times m$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含棋盘上的最大棋盘图案数量。

在接下来的 (n) 行中，以输入格式相同的方式输出上色后的棋盘。输出的棋盘应满足以下条件：

• 只包含 B 和 W。
• 如果输入中的格子已经上色，则在输出中不能改变其颜色。
• 棋盘图案的数量等于你打印的答案。

如果有多种解决方案，输出其中任何一种。

3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?

1
WB
BW
1
BWB
WWB
BBW
4
BWB
WBW
BWB