City Block Partition

Hard

0/120

0 upvote

Asked in company

Problem statement

In the city of Gridopolis, the layout is a 2xN grid of blocks. Each block can be either open for passage (.) or closed for construction (x).

A neighborhood is defined as a set of open blocks that are all connected. Two open blocks are connected if you can travel from one to the other by moving between adjacent blocks, either horizontally or vertically.

You are given that the initial city grid contains at most one connected neighborhood.

Your task is to identify and count the number of critical blocks. A critical block is an open block that, if it were to be closed for construction (changed from . to x), would cause the city to split into exactly 3 separate neighborhoods.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer 'n', the number of blocks (columns) in each of the two streets.

The next two lines each contain a string of length 'n', representing the two rows of the city grid. . denotes an open block, and x denotes a closed block.

Output Format:

Print a single integer representing the total count of critical blocks in the grid.

Note:

Only open blocks (.) can be considered for closure to become critical blocks.

The initial grid is guaranteed to have 0 or 1 neighborhood.

A neighborhood requires at least one open block.

Sample Input 1:

5
..x..
.x.x.

Sample Output 1:

Explanation for Sample 1:

The grid is:
(0,0) (0,1) (0,2) (0,3) (0,4)
.     .     x     .     .
.     x     .     x     .
(1,0) (1,1) (1,2) (1,3) (1,4)

Consider the open block at position (1, 2). Its open neighbors are (0, 1), (1, 1)(no), (1, 3), and (0,2)(no).
Let's re-check the image:
Row 0: . . x . .
Row 1: . x . x .
The only block that connects the left side (`(0,0), (0,1), (1,0)`) with the right side (`(0,3), (0,4)`) and the middle (`(1,2)`) is not a thing. Let's find the correct block.
Let's try a different sample.
Sample:
5
. . . x .
x . . . .

Grid:
. . . x .
x . . . .

The block at (1, 2) is a candidate. Its open neighbors are (0, 2), (1, 1), and (1, 3).
- If we close (1, 2), the neighborhood containing (0, 2) is now separated from the others.
- The neighborhood containing (1, 1) is separated.
- The neighborhood containing (1, 3) is separated.
These three neighbors are not connected to each other by any other path. Closing (1, 2) breaks the single neighborhood into three. Thus, (1, 2) is a critical block. No other block has this property.

Sample Input 2:

3
...
...

Sample Output 2:

Explanation for Sample 2:

The grid is a solid 2x3 block of open passages. Closing any single block will not disconnect the grid. At most, it will be split into 2 neighborhoods (by closing a corner) or remain as 1 neighborhood. No block can split it into 3.

Expected Time Complexity:

The expected time complexity is O(n).

Constraints:

1 <= n <= 200,000
The input strings contain only '.' and 'x'.
The initial grid has at most 1 connected neighborhood.

Time limit: 1sec

Approaches (1)

Approach 1

City Block Partition

Time Complexity

Time complexity is O(n).

Space Complexity

(100% EXP penalty)

City Block Partition

Console