1997B.md (2325B)
1 Source: https://codeforces.com/problemset/problem/1997/B 2 3 B. Make Three Regions 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 There is a grid, consisting of $2$ rows and $n$ columns. Each cell of the grid is either free or blocked. 22 23 A free cell $y$ is reachable from a free cell $x$ if at least one of these conditions holds: 24 25 * $x$ and $y$ share a side; 26 * there exists a free cell $z$ such that $z$ is reachable from $x$ and $y$ is reachable from $z$. 27 28 A connected region is a set of free cells of the grid such that all cells in it are reachable from one another, but adding any other free cell to the set violates this rule. 29 30 For example, consider the following layout, where white cells are free, and dark grey cells are blocked: 31 32  33 34 There are $3$ regions in it, denoted with red, green and blue color respectively: 35 36  37 38 The given grid contains at most $1$ connected region. Your task is to calculate the number of free cells meeting the following constraint: 39 40 * if this cell is blocked, the number of connected regions becomes exactly $3$. 41 42 Input 43 44 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 45 46 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of columns. 47 48 The $i$-th of the next two lines contains a description of the $i$-th row of the grid — the string $s_i$, consisting of $n$ characters. Each character is either . (denoting a free cell) or x (denoting a blocked cell). 49 50 Additional constraint on the input: 51 52 * the given grid contains at most $1$ connected region; 53 * the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 54 55 Output 56 57 For each test case, print a single integer — the number of cells such that the number of connected regions becomes $3$ if this cell is blocked. 58 59 Example 60 61 Input 62 63 ``` 64 4 65 66 8 67 68 .......x 69 70 .x.xx... 71 72 2 73 74 .. 75 76 .. 77 78 3 79 80 xxx 81 82 xxx 83 84 9 85 86 ..x.x.x.x 87 88 x.......x 89 ``` 90 91 Output 92 93 ``` 94 1 95 0 96 0 97 2 98 ``` 99 100 Note 101 102 In the first test case, if the cell $(1, 3)$ is blocked, the number of connected regions becomes $3$ (as shown in the picture from the statement).