Make Connected

The fake-hard part is connectivity. You might think we need to search for some custom way to connect all components. Nope. The final connected shape is extremely restricted.

Classifying valid shapes

Treat black cells as vertices of a graph, with edges between orthogonally adjacent black cells.

In a valid final grid, no cell can have black neighbors on both sides horizontally:

###

That would be illegal. Same vertically.

So every black cell has degree at most $2$. Also, if a cell has degree $2$, the two edges must be perpendicular. A straight-through cell would again make three consecutive black cells.

That means any connected final shape is basically a path or a tiny cycle, and every internal step must turn.

Now look at a path of cells. Consecutive moves must alternate between horizontal and vertical. Suppose the path moves right, then vertically, then left. Those four cells form a $2\times2$ block. After that, trying to continue either closes that exact $2\times2$ block or creates three cells in one row/column. So a shape that is not contained in a $2\times2$ block cannot reverse horizontal direction. By the same argument, it cannot reverse vertical direction either.

Therefore, any larger valid connected shape uses only two directions, like right+down, right+up, left+down, or left+up. That is exactly a diagonal staircase.

A staircase using right+down or left+up stays on two adjacent values of $r-c$.

A staircase using right+up or left+down stays on two adjacent values of $r+c$.

So every possible final shape is one of these three types:

1. inside a $2\times2$ rectangle;
2. inside two adjacent diagonals $r-c=k$ and $r-c=k+1$;
3. inside two adjacent anti-diagonals $r+c=k$ and $r+c=k+1$.

Since the original black cells must be a subset of the final shape, they must fit one of those three cages. That gives necessity.

Why the checks are enough

If all black cells fit in a $2\times2$ rectangle, paint that whole rectangle black. Connected, and no line of length $3$.

If all black cells fit in two adjacent $r-c$ diagonals, paint the missing cells in that strip between the needed endpoints. It becomes a staircase like:

##..
.##.
..##

Every row and every column has at most two black cells from the strip, and the strip is connected.

For two adjacent $r+c$ diagonals, it is the same picture mirrored:

..##
.##.
##..

So the implementation just scans the original # cells and records ranges.

For black cells $(r,c)$, compute:

• row range: $\max r-\min r$;
• column range: $\max c-\min c$;
• main diagonal range: $\max(r-c)-\min(r-c)$;
• anti-diagonal range: $\max(r+c)-\min(r+c)$.

Then answer YES if:

or

or

The empty grid is also YES, because we can paint any one cell black. With the usual infinity initialization, it falls out naturally.

Complexity is $O(n^2)$ per test case and $O(1)$ extra memory. Very small, very clean, no graph-search circus required.