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 ```
给你一个 $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 ```