← 返回题目列表

Codeforces · 1766/C

C. 哈密顿墙

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

Monocarp Hamilton 爵士正计划粉刷他的墙壁。墙可以表示为一个网格,由 $$$2$$$ 行和 $$$m$$$ 列组成。最初,墙壁是完全白色的。

Monocarp 想在墙上画一幅黑色的画。特别是,如果 $$$c_{i, j} =$$$ 'B',他希望单元格 $$$(i, j)$$$(第 $$$i$$$ 行中的 $$$j$$$-th 单元格)为黑色,如果 $$$c_{i, j} =$$$ 'W',则为白色。此外,他希望每一列至少有一个黑色单元格,因此,对于每个 $$$j$$$,满足以下约束:$$$c_{1, j}$$$、$$$c_{2, j}$$$ 或两者都等于 'B'。

为了使图片变得平滑,Monocarp 希望在某个单元格 $$$(x_1, y_1)$$$ 中放置一个画笔,并沿着路径 $$$(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$$$ 移动它,以便:

- 对于每个 $$$i$$$、$$$(x_i, y_i)$$$ 和 $$$(x_{i+1}, y_{i+1})$$$ 共享公共边;
- 所有黑色单元格在路径中只出现一次;
- 白色单元格不会出现在路径中。

确定 Monocarp 是否可以粉刷墙壁。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 墙中的列数。

接下来两行的第 $$$i$$$ 包含字符串 $$$c_i$$$,由 $$$m$$$ 个字符组成,其中每个字符为“B”或“W”。如果单元格 $$$(i, j)$$$ 应为黑色,则 $$$c_{i, j}$$$ 为“B”;如果单元格 $$$(i, j)$$$ 应为白色,则 $$$c_{i, j}$$$ 为“W”。

此外,对于每个 $$$j$$$,满足以下约束:$$$c_{1, j}$$$、$$$c_{2, j}$$$ 或两者都等于 'B'。

所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果 Monocarp 可以粉刷墙壁,则打印“YES”。否则,打印“NO”。

示例

输入 #1

6
3
WBB
BBW
1
B
B
5
BWBWB
BBBBB
2
BW
WB
5
BBBBW
BWBBB
6
BWBBWB
BBBBBB

输出 #1

YES
YES
NO
NO
NO
YES

注意

在第一个测试用例中,Monocarp 可以用画笔沿着路径 $$$(2, 1)$$$、$$$(2, 2)$$$、$$$(1, 2)$$$、$$$(1, 3)$$$ 移动。所有黑色单元在路径中只出现一次,路径中没有白色单元出现。

在第二个测试用例中,Monocarp 可以遵循路径 $$$(1, 1)$$$, $$$(2, 1)$$$。

在第三个测试用例中:

- 路径 $$$(1, 1)$$$、$$$(2, 1)$$$、$$$(2, 2)$$$、$$$(2, 3)$$$、$$$(1, 3)$$$、$$$(2, 4)$$$、$$$(2, 5)$$$、$$$(1, 5)$$$还不够,因为一对单元格 $$$(1, 3)$$$ 和 $$$(2, 4)$$$ 不共享公共边;
- 路径 $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ 不够,因为单元格 $$$(2, 3)$$$ 被访问了两次;
- 路径 $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$ 不够,因为黑色单元格$$$(1, 3)$$$ 没有出现在路径中;
- 路径 $$$(1, 1)$$$, $$$(2, 1)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(1, 5)$$$, $$$(1, 4)$$$, $$$(1, 3)$$$ 不够,因为路径中出现了一个白色单元格 $$$(1, 4)$$$。