372. Counting Islands
A grid of 0 and 1 characters is given. A 1 is land and a 0 is water.
Two land cells belong to the same island when they share an edge, meaning they
are directly above, below, left or right of one another. Diagonal touching does
NOT connect them.
Print the number of islands.
This is problem 363, connected components, on a graph nobody built. There is no edge list here: the neighbours of a cell are wherever the four directions land, so the adjacency is computed rather than stored. That is the idea worth taking away, because most real graphs arrive this way.
The diagonal rule is the whole first sample. Five 1 cells arranged like the
face of a die touch only at corners, so the answer is 5, not 1.
Constraints - `1 ≤ r ≤ 1000` - `1 ≤ c ≤ 1000` - Every character is `0` or `1`.
Input
The first line contains two integers r and c, the number of rows and
columns. Each of the next r lines contains c characters, each 0 or 1,
with no spaces between them.
Output
Print one integer, the number of islands.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.