CF2181K Knit the Grid

伏都教女巫曾经编织过一块神奇的挂毯。起初，她拿了一块空白画布，可以表示为一个 $r \times c$ 的网格，有 $r$ 行和 $c$ 列，因此共有 $(r + 1) \times (c + 1)$ 个网格点。然后，她进行了若干次以下操作：在画布上沿网格线编织一个圈（闭合回路），该圈在编织过程中每个网格点最多经过一次。此外，任意两个圈都不共享任何网格点。 最后结果显示，不位于画布边界上的 $(r-1) \cdot (c-1)$ 个内部网格点中，每一个都恰好被一个圈经过。以下是 $r=2, c=3$ 时的一些圈排列示例，图中高亮显示了内部网格点：    随后，她将画布留在地板上过夜。夜里，有 $r \cdot c$ 只绿色的青蛙跳上了画布，每个单元格里坐一只。但这只是女巫麻烦的开始！因为接着，老巫婆来到了画布前，一根接一根地拆掉了画布上所有编织好的线条。每当她拆掉两个相邻网格点之间的一段编织线段时，与该线段相邻的单元格中的青蛙就会受到惊吓（根据线段是否在边界上，会有 $1$ 只或 $2$ 只青蛙受惊）。当一只青蛙受惊时，它会立即改变颜色：如果它是绿色的，就会变成棕色；如果是棕色的，就会变回绿色。 如果圈的排列如上图所示，那么青蛙的颜色将如下所示（灰色单元格代表绿色青蛙，白色单元格代表棕色青蛙）：    当伏都教女巫回到画布前时，她只看到画布上有两种颜色的青蛙，但编织的圈都不见了。根据给定的青蛙颜色排列，请判断它是否可能由上述过程产生；如果可能，请帮助女巫还原出一种可能的圈排列方案。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。 每个测试用例的第一行包含两个整数 $r$ 和 $c$，表示网格的尺寸 ($2 \le r, c \le 10^3$)。 接下来的 $r$ 行，每行包含一个由 $c$ 个字符 'G' 或 'B' 组成的字符串，分别代表绿色（Green）和棕色（Brown）的青蛙。 保证所有测试用例中 $r \cdot c$ 的总和不超过 $2 \cdot 10^6$。

对于每个测试用例，如果给定的青蛙颜色可以由上述过程产生，则在第一行输出 `YES`，否则输出 `NO`。 如果答案为 `YES`，则额外输出 $2r+1$ 行由 $0$ 和 $1$ 字符组成的二进制字符串。 - 前 $r+1$ 行：每行长度为 $c$，表示水平网格线段。第 $i$ 行第 $j$ 个字符为 $1$ 表示对应的水平线段上有编织线，$0$ 表示没有。 - 后 $r$ 行：每行长度为 $c+1$，表示垂直网格线段。第 $i$ 行第 $j$ 个字符为 $1$ 表示对应的垂直线段上有编织线，$0$ 表示没有。

第一个测试用例是题目描述中第一个圈排列示例。 在第二个样例测试用例中，输出显示的方案在下方第一张图中给出。第二张图的圈排列也是正确的，而第三张图是错误的，因为有些网格点被多个圈共享。让网格留空也是不正确的，因为必须有圈经过所有内部网格点。    翻译由 Gemini3.0 flash 完成。