998. Regions of One Colour

A map is a grid of r rows and c columns, and every cell is painted one lowercase letter. Two cells belong to the same REGION when they share a side and carry the same letter. Sharing only a corner does not join them.

Print how many regions the map has. Every cell belongs to exactly one region, so the regions cover the whole map.

aab abab aaaa ab abb -> 3 abab -> 4 abba -> 2 ba -> 4 ccc (2 by 4) aaaa (2 by 2)

The first map has one region of a shaped like a corner, one of b shaped like a corner the other way up, and the bottom row of c. The last map is a chequerboard, where the two a cells touch only at a corner, so there are four regions and not two.

## What most people try first

Recursive flood fill from every cell not yet claimed. The idea is right and the recursion is not: a 1000 by 1000 map painted one colour is 10^6 cells in a single region, so the recursion goes a million frames deep and the stack runs out long before the answer does. A queue fixes that, and this problem is written to show the version that needs neither.

## Sweep once, joining up and left only

Number the cell in row i and column j as i * c + j. Then

regions = r * c for i in 0 .. r-1: for j in 0 .. c-1: if i > 0 and grid[i-1][j] == grid[i][j] and union succeeded: regions = regions - 1 if j > 0 and grid[i][j-1] == grid[i][j] and union succeeded: regions = regions - 1 print regions

No visited array, no queue, no recursion, and the whole map is read once.

## Why looking only up and left is enough

The regions are the connected pieces of the graph whose vertices are cells and whose edges join equal-letter neighbours. Every such edge is either vertical or horizontal, and every edge is considered exactly once: a vertical edge when its LOWER cell is reached, a horizontal edge when its RIGHT cell is reached. Looking at all four directions instead would consider each edge twice, which costs time but changes no answer, because a second merge of two cells already together does nothing.

## Why counting down from r * c is right

Each cell starts as its own region, which is r * c of them. A merge that genuinely joins two different regions replaces two with one. A merge whose two cells already share a root must not be counted, which is what testing the return value of the union does; on the map aa over aa the fourth edge closes a square and joins nothing new.

## Overflow

r * c reaches 10^6, which is comfortably inside a signed 32 bit integer, whose maximum is 2147483647. Nothing here needs 64 bits. What DOES matter is memory: two arrays of 10^6 integers is about 8 megabytes, and allocating a two dimensional array of that size per row by mistake is what actually runs out.

## Cross-reference

Problem 372 counts islands on a grid of 0 and 1, where only the 1 cells form islands and the 0 cells are water that is never counted. Here every cell belongs to a region, so the equivalent of the water is counted too, and the letters may be any of 26 rather than two. Problem 1035 runs this exact up-and-left sweep and asks a different question of it: whether any region contains a closed loop.

## Cost

Time O(r c alpha(r c)). Space O(r c).

Constraints - `1 ≤ r ≤ 1000` - `1 ≤ c ≤ 1000` - Every character is a lowercase English letter.