309974: CF1766C. Hamiltonian Wall

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Hamiltonian Wall

题意翻译

给你一个 $2\times m$ 的矩阵,矩阵中只可能包含字符 `B` 和 `W`。每一列都有字符 `B`。问能否找出一条路径,满足: - 路径中相邻两格有公共边(只有公共点的不算)。 - 每个 `B` 格恰好被覆盖一次。 - 每个 `W` 格都没有被覆盖到。 如果存在这样的路径,输出 `YES`,否则输出 `NO`。

题目描述

Sir Monocarp Hamilton is planning to paint his wall. The wall can be represented as a grid, consisting of $ 2 $ rows and $ m $ columns. Initially, the wall is completely white. Monocarp wants to paint a black picture on the wall. In particular, he wants cell $ (i, j) $ (the $ j $ -th cell in the $ i $ -th row) to be colored black, if $ c_{i, j} = $ 'B', and to be left white, if $ c_{i, j} = $ 'W'. Additionally, he wants each column to have at least one black cell, so, for each $ j $ , the following constraint is satisfied: $ c_{1, j} $ , $ c_{2, j} $ or both of them will be equal to 'B'. In order for the picture to turn out smooth, Monocarp wants to place down a paint brush in some cell $ (x_1, y_1) $ and move it along the path $ (x_1, y_1), (x_2, y_2), \dots, (x_k, y_k) $ so that: - for each $ i $ , $ (x_i, y_i) $ and $ (x_{i+1}, y_{i+1}) $ share a common side; - all black cells appear in the path exactly once; - white cells don't appear in the path. Determine if Monocarp can paint the wall.

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ m $ ( $ 1 \le m \le 2 \cdot 10^5 $ ) — the number of columns in the wall. The $ i $ -th of the next two lines contains a string $ c_i $ , consisting of $ m $ characters, where each character is either 'B' or 'W'. $ c_{i, j} $ is 'B', if the cell $ (i, j) $ should be colored black, and 'W', if the cell $ (i, j) $ should be left white. Additionally, for each $ j $ , the following constraint is satisfied: $ c_{1, j} $ , $ c_{2, j} $ or both of them are equal to 'B'. The sum of $ m $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式


For each testcase, print "YES" if Monocarp can paint a wall. Otherwise, print "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

说明

In the first testcase, Monocarp can follow a path $ (2, 1) $ , $ (2, 2) $ , $ (1, 2) $ , $ (1, 3) $ with his brush. All black cells appear in the path exactly once, no white cells appear in the path. In the second testcase, Monocarp can follow a path $ (1, 1) $ , $ (2, 1) $ . In the third testcase: - the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (1, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ doesn't suffice because a pair of cells $ (1, 3) $ and $ (2, 4) $ doesn't share a common side; - the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (1, 3) $ , $ (2, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ doesn't suffice because cell $ (2, 3) $ is visited twice; - the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ doesn't suffice because a black cell $ (1, 3) $ doesn't appear in the path; - the path $ (1, 1) $ , $ (2, 1) $ , $ (2, 2) $ , $ (2, 3) $ , $ (2, 4) $ , $ (2, 5) $ , $ (1, 5) $ , $ (1, 4) $ , $ (1, 3) $ doesn't suffice because a white cell $ (1, 4) $ appears in the path.

Input

题意翻译

给你一个 $2\times m$ 的矩阵,矩阵中只可能包含字符 `B` 和 `W`。每一列都有字符 `B`。问能否找出一条路径,满足: - 路径中相邻两格有公共边(只有公共点的不算)。 - 每个 `B` 格恰好被覆盖一次。 - 每个 `W` 格都没有被覆盖到。 如果存在这样的路径,输出 `YES`,否则输出 `NO`。

Output

**题意翻译**

给你一个 $2 \times m$ 的矩阵,矩阵中只可能包含字符 `B` 和 `W`。每一列都有字符 `B`。问能否找出一条路径,满足:

- 路径中相邻两格有公共边(只有公共点的不算)。
- 每个 `B` 格恰好被覆盖一次。
- 每个 `W` 格都没有被覆盖到。

如果存在这样的路径,输出 `YES`,否则输出 `NO`。

**题目描述**

Sir Monocarp Hamilton is planning to paint his wall. The wall can be represented as a grid, consisting of $2$ rows and $m$ columns. Initially, the wall is completely white.

Monocarp wants to paint a black picture on the wall. In particular, he wants cell $(i, j)$ (the $j$-th cell in the $i$-th row) to be colored black, if $c_{i, j} = $ 'B', and to be left white, if $c_{i, j} = $ 'W'. Additionally, he wants each column to have at least one black cell, so, for each $j$, the following constraint is satisfied: $c_{1, j}$, $c_{2, j}$ or both of them will be equal to 'B'.

In order for the picture to turn out smooth, Monocarp wants to place down a paint brush in some cell $(x_1, y_1)$ and move it along the path $(x_1, y_1)$, $(x_2, y_2)$, ..., $(x_k, y_k)$ so that:

- for each $i$, $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ share a common side;
- all black cells appear in the path exactly once;
- white cells don't appear in the path.

Determine if Monocarp can paint the wall.

**输入输出格式**

**输入格式**

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

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

接下来两行,每行包含一个由 'B' 和 'W' 组成的字符串 $c_i$,表示对应行的每个单元格的颜色。对于每个 $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
```**题意翻译** 给你一个 $2 \times m$ 的矩阵,矩阵中只可能包含字符 `B` 和 `W`。每一列都有字符 `B`。问能否找出一条路径,满足: - 路径中相邻两格有公共边(只有公共点的不算)。 - 每个 `B` 格恰好被覆盖一次。 - 每个 `W` 格都没有被覆盖到。 如果存在这样的路径,输出 `YES`,否则输出 `NO`。 **题目描述** Sir Monocarp Hamilton is planning to paint his wall. The wall can be represented as a grid, consisting of $2$ rows and $m$ columns. Initially, the wall is completely white. Monocarp wants to paint a black picture on the wall. In particular, he wants cell $(i, j)$ (the $j$-th cell in the $i$-th row) to be colored black, if $c_{i, j} = $ 'B', and to be left white, if $c_{i, j} = $ 'W'. Additionally, he wants each column to have at least one black cell, so, for each $j$, the following constraint is satisfied: $c_{1, j}$, $c_{2, j}$ or both of them will be equal to 'B'. In order for the picture to turn out smooth, Monocarp wants to place down a paint brush in some cell $(x_1, y_1)$ and move it along the path $(x_1, y_1)$, $(x_2, y_2)$, ..., $(x_k, y_k)$ so that: - for each $i$, $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ share a common side; - all black cells appear in the path exactly once; - white cells don't appear in the path. Determine if Monocarp can paint the wall. **输入输出格式** **输入格式** 第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。 每个测试用例的第一行包含一个整数 $m$ ($1 \le m \le 2 \cdot 10^5$) — 墙的列数。 接下来两行,每行包含一个由 'B' 和 'W' 组成的字符串 $c_i$,表示对应行的每个单元格的颜色。对于每个 $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 ```

加入题单

上一题 下一题 算法标签: