← 返回题目列表

Codeforces · 1863/D

D. 两种颜色的多米诺骨牌

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

有一块 $$$n\times m$$$ 的棋盘,分为多个单元。这个板上还有一些多米诺骨牌。每个多米诺骨牌覆盖两个相邻的单元格(即共享一条边的两个单元格),并且没有两个多米诺骨牌重叠。

Piet 认为这块板子太无聊了,需要重新上漆。他会将多米诺骨牌的单元格涂成黑色和白色。如果满足以下所有条件,他称这幅画为美丽的:

- 对于每个多米诺骨牌,其一个单元格被漆成白色,另一个单元格被漆成黑色;
- 对于每一行,该行中黑色单元格的数量等于该行中白色单元格的数量;
- 对于每一列,该列中黑色单元格的数量等于该列中白色单元格的数量。

请注意,没有被多米诺骨牌覆盖的单元格根本不被绘制,它们既不被视为黑色也不被视为白色。

帮助皮特创作一幅美丽的画作,或者告诉他这是不可能的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
4 6
..LR..
ULRU..
DLRDUU
..LRDD
5 4
.LR.
.UU.
UDDU
D..D
LR..
2 2
..
..

输出 #1

..WB..
WWBB..
BBWWWB
..BWBW
-1
..
..

注意

在第一个测试用例中,答案如下所示:

在第二个测试用例中,不可能以正确的方式绘制所有单元格。