[EC Final 2021] Check Pattern is Good
题意翻译
#### 题目描述
教授 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`。
* 如果输入中的格子已经上色,则在输出中不能改变其颜色。
* 棋盘图案的数量等于你打印的答案。
如果有多种解决方案,输出其中任何一种。
题目描述
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:
```plain
BW
WB
```
```plain
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.
输入输出样例
输入样例 #1
3
2 2
??
??
3 3
BW?
W?B
?BW
3 3
BW?
W?W
?W?
输出样例 #1
1
WB
BW
1
BWB
WWB
BBW
4
BWB
WBW
BWB