1766C.md (3045B)
1 Source: https://codeforces.com/problemset/problem/1766/C 2 3 C. Hamiltonian Wall 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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. 22 23 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'. 24 25 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: 26 27 * for each $i$, $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$ share a common side; 28 * all black cells appear in the path exactly once; 29 * white cells don't appear in the path. 30 31 Determine if Monocarp can paint the wall. 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases. 36 37 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. 38 39 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. 40 41 Additionally, for each $j$, the following constraint is satisfied: $c_{1, j}$, $c_{2, j}$ or both of them are equal to 'B'. 42 43 The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each testcase, print "YES" if Monocarp can paint a wall. Otherwise, print "NO". 48 49 Example 50 51 Input 52 53 ``` 54 6 55 56 3 57 58 WBB 59 60 BBW 61 62 1 63 64 B 65 66 B 67 68 5 69 70 BWBWB 71 72 BBBBB 73 74 2 75 76 BW 77 78 WB 79 80 5 81 82 BBBBW 83 84 BWBBB 85 86 6 87 88 BWBBWB 89 90 BBBBBB 91 ``` 92 93 Output 94 95 ``` 96 YES 97 YES 98 NO 99 NO 100 NO 101 YES 102 ``` 103 104 Note 105 106 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. 107 108 In the second testcase, Monocarp can follow a path $(1, 1)$, $(2, 1)$. 109 110 In the third testcase: 111 112 * 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; 113 * 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; 114 * 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; 115 * 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.