310635: CF1863D. Two-Colored Dominoes
Description
There is an $n\times m$ board divided into cells. There are also some dominoes on this board. Each domino covers two adjacent cells (that is, two cells that share a side), and no two dominoes overlap.
Piet thinks that this board is too boring and it needs to be painted. He will paint the cells of the dominoes black and white. He calls the painting beautiful if all of the following conditions hold:
- for each domino, one of its cells is painted white and the other is painted black;
- for each row, the number of black cells in this row equals the number of white cells in this row;
- for each column, the number of black cells in this column equals the number of white cells in this column.
Note that the cells that are not covered by dominoes are not painted at all, they are counted as neither black nor white.
Help Piet produce a beautiful painting or tell that it is impossible.
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ ($2\le n, m\le 500$).
The next $n$ lines describe the tiling of the board, row by row from top to bottom. Each of these lines contains $m$ characters, describing the cells in the corresponding row from left to right. Each character is one of U, D, L, R, or ., meaning that the cell is covered with a top, bottom, left, right half of a domino or nothing, respectively. The tiling is guaranteed to be valid.
It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $250\,000$.
OutputFor each test case, output a single integer $-1$ if a beautiful painting does not exist. Otherwise, print $n$ lines, each containing $m$ characters, describing the colors in the corresponding row of a beautiful painting. Every character corresponding to a cell not covered by a domino must be . (a dot), and all other characters must be B if the corresponding cell is black or W if it is white.
If there are multiple solutions, print any of them.
ExampleInput3 4 6 ..LR.. ULRU.. DLRDUU ..LRDD 5 4 .LR. .UU. UDDU D..D LR.. 2 2 .. ..Output
..WB.. WWBB.. BBWWWB ..BWBW -1 .. ..Note
In the first test case, the answer is illustrated below:
In the second test case, it is impossible to paint all cells the right way.
Output
有一个 $ n \times m $ 的棋盘，被分割成许多小方格，棋盘上放置了一些多米诺骨牌。每个多米诺骨牌覆盖两个相邻的方格（即共享边的两个方格），并且没有两个多米诺骨牌重叠。
皮特认为这个棋盘太无聊了，需要上色。他将多米诺骨牌的方格涂成黑色和白色。如果满足以下所有条件，他称之为“美丽”的涂法：
- 对于每个多米诺骨牌，它的两个方格中一个被涂成白色，另一个被涂成黑色；
- 对于每一行，该行中黑色方格的数量等于白色方格的数量；
- 对于每一列，该列中黑色方格的数量等于白色方格的数量。
注意，没有被多米诺骨牌覆盖的方格不会被涂色，它们既不算作黑色也不算作白色。
帮助皮特完成一个美丽的涂法，或者指出这是不可能的。
输入数据格式：
- 输入包含多个测试用例。第一行包含测试用例的数量 $ t $（$ 1 \le t \le 10,000 $）。
- 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 2 \le n, m \le 500 $）。
- 接下来的 $ n $ 行描述了棋盘的铺设，从上到下逐行描述。每行包含 $ m $ 个字符，从左到右描述相应的行中方格。每个字符是以下之一：U、D、L、R 或 .，分别表示方格被多米诺骨牌的上半部分、下半部分、左半部分、右半部分覆盖或者没有覆盖。铺设保证是有效的。
- 保证所有测试用例的 $ n \cdot m $ 之和不超过 $ 250,000 $。
输出数据格式：
- 对于每个测试用例，如果不存在美丽的涂法，输出一个整数 -1。否则，输出 $ n $ 行，每行包含 $ m $ 个字符，描述美丽涂法中对应行的颜色。没有被多米诺骨牌覆盖的方格对应的字符必须是 .（一个点），其他所有字符必须是 B 如果对应的方格是黑色或者 W 如果是白色。
- 如果有多个解，输出其中任意一个。题目大意：双色多米诺骨牌 有一个 $ n \times m $ 的棋盘，被分割成许多小方格，棋盘上放置了一些多米诺骨牌。每个多米诺骨牌覆盖两个相邻的方格（即共享边的两个方格），并且没有两个多米诺骨牌重叠。 皮特认为这个棋盘太无聊了，需要上色。他将多米诺骨牌的方格涂成黑色和白色。如果满足以下所有条件，他称之为“美丽”的涂法： - 对于每个多米诺骨牌，它的两个方格中一个被涂成白色，另一个被涂成黑色； - 对于每一行，该行中黑色方格的数量等于白色方格的数量； - 对于每一列，该列中黑色方格的数量等于白色方格的数量。 注意，没有被多米诺骨牌覆盖的方格不会被涂色，它们既不算作黑色也不算作白色。 帮助皮特完成一个美丽的涂法，或者指出这是不可能的。 输入数据格式： - 输入包含多个测试用例。第一行包含测试用例的数量 $ t $（$ 1 \le t \le 10,000 $）。 - 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 2 \le n, m \le 500 $）。 - 接下来的 $ n $ 行描述了棋盘的铺设，从上到下逐行描述。每行包含 $ m $ 个字符，从左到右描述相应的行中方格。每个字符是以下之一：U、D、L、R 或 .，分别表示方格被多米诺骨牌的上半部分、下半部分、左半部分、右半部分覆盖或者没有覆盖。铺设保证是有效的。 - 保证所有测试用例的 $ n \cdot m $ 之和不超过 $ 250,000 $。 输出数据格式： - 对于每个测试用例，如果不存在美丽的涂法，输出一个整数 -1。否则，输出 $ n $ 行，每行包含 $ m $ 个字符，描述美丽涂法中对应行的颜色。没有被多米诺骨牌覆盖的方格对应的字符必须是 .（一个点），其他所有字符必须是 B 如果对应的方格是黑色或者 W 如果是白色。 - 如果有多个解，输出其中任意一个。