CF1863D Two-Colored Dominoes

有一个 $n \times m$ 的棋盘，被划分为若干个格子。棋盘上还放置了一些多米诺骨牌。每个多米诺骨牌覆盖两个相邻的格子（即两个有公共边的格子），且任意两个多米诺骨牌没有重叠。 Piet 觉得这个棋盘太无聊了，需要给它涂色。他打算将多米诺骨牌覆盖的格子涂成黑色和白色。他称涂色是美丽的，当且仅当满足以下所有条件： - 对于每个多米诺骨牌，其覆盖的两个格子中有一个被涂成白色，另一个被涂成黑色； - 对于每一行，该行中黑色格子的数量等于白色格子的数量； - 对于每一列，该列中黑色格子的数量等于白色格子的数量。 注意，没有被多米诺骨牌覆盖的格子不进行涂色，也不计入黑色或白色格子的数量。 请你帮助 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 表示白色。 如果有多种方案，输出任意一种均可。

在第一个测试用例中，答案如下图所示：  在第二个测试用例中，不可能将所有格子按要求正确涂色。 由 ChatGPT 4.1 翻译