codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/ec3a2cd65e8391fb5879ea5d46f2631867debbdc.png) 
     33 
     34 There are $3$ regions in it, denoted with red, green and blue color respectively:
     35 
     36  ![](https://espresso.codeforces.com/51f122c2526949beaf2bea6d86b680011376a1f1.png) 
     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).