1002. Regions Cut by Strokes

A square board is divided into n by n cells. Each cell holds one of three things:

0 nothing 1 a stroke from the bottom left corner of the cell to its top right corner 2 a stroke from the top left corner of the cell to its bottom right corner

The strokes cut the square into separate regions. Print how many regions there are.

0 1 0 1 1 2 1 2 0 -> 2 0 0 -> 1 2 1 -> 5 -> 2 (one cell, one stroke)

The third board is the one to picture: a stroke up-right in the top left cell, a stroke down-right beside it, and the mirror image below. The four strokes close a diamond in the middle of the square, so there are the four corner pieces and the diamond, five in all.

Turn that same board the other way round, 2 1 over 1 2, and the four strokes meet at the centre point instead. Nothing is enclosed and the answer is 4.

## What most people try first

Treat each cell as one element and join neighbours that are not separated. That cannot work, because a stroke cuts a CELL, so a cell is not a single thing to be joined or not. A board of one cell with one stroke answers 2, and no method that treats a cell as an atom will ever print 2.

The next idea usually works: blow each cell up into a block of S by S pixels, draw the stroke as blocked pixels along the block's diagonal, and flood fill what is left. It is correct from S = 3 upward. It is NOT correct at S = 2: on a random board of 3 by 3 cells it disagrees with the true answer about half the time, because at that scale a stroke touches both pixels of the block's diagonal and seals off pieces that should still be joined. It also costs S^2 times the memory.

## Four triangles per cell

Cut every cell along BOTH its diagonals into four triangles, numbered

0 = top, 1 = right, 2 = bottom, 3 = left

so cell (i, j) owns elements 4(i n + j) + 0 .. 3. Then the strokes say which triangles of a cell are joined:

nothing: join 0-1, 1-2, 2-3 the whole cell is one piece stroke 1: join 0-3 and 1-2 the up-right stroke keeps top with left stroke 2: join 0-1 and 2-3 the down-right stroke keeps top with right

and the cell borders say which triangles of different cells are joined, with no condition at all because a border is never a wall:

right neighbour: triangle 1 of (i, j) with triangle 3 of (i, j+1) lower neighbour: triangle 2 of (i, j) with triangle 0 of (i+1, j)

Start the count at 4 n^2 and subtract one per genuine merge.

## Why four triangles are enough

A stroke runs corner to corner, so within one cell it can separate the four triangles in only the two ways listed, and it never cuts a triangle into smaller pieces. Two points of the square are in the same region exactly when there is a path between them that crosses no stroke, and any such path can be pushed into a walk through triangles that share an uncut edge, which is precisely the joins above. So the regions are the groups of the structure.

## The two joins that are easy to get backwards

Stroke 1 goes from the bottom left up to the top right. The piece ABOVE it holds the top and the LEFT triangles, so the joins are 0 with 3 and 1 with 2. Writing 0 with 1 there is stroke 2's rule and produces 4 on the diamond board instead of 5.

Across a border, the right triangle of one cell meets the LEFT triangle of its neighbour, not its right triangle. Getting that wrong joins the wrong pieces and generally lowers the count.

## Overflow

4 n^2 reaches 10^6 at n = 500, which is well inside a signed 32 bit integer whose maximum is 2147483647.

## Cross-reference

Problem 998 counts regions on a grid where a cell is a single unit. This problem is what happens when a cell is not, and the technique of splitting one element of the input into several elements of the structure is the transferable part.

## Cost

Time O(n^2 alpha(n^2)). Space O(n^2).

Constraints - `1 ≤ n ≤ 500` - Every value is `0`, `1` or `2`.