Number of Islands

A map arrives as a list of rows of equal length. Every character is either 1, a square of land, or 0, a square of water. Two land squares belong to the same island when one sits directly above, below, left or right of the other. Squares that only touch at a corner are not connected.

Take the map ["11000", "11000", "00100", "00011"]:

• the four land squares in the top left corner form one island,
• the single square in the middle row is a second island, since it only touches the first one at a corner,
• the two squares in the bottom right form a third.

So the map holds 3 islands.

The map is really a graph: each land square is a node, and an edge joins two land squares that share a side. Counting islands means counting the connected pieces of that graph. Every time you find a land square you have not visited yet, you have found a new island, and you explore all of it before moving on.

Write a function named numIslands that gets grid, a list of strings made of 1 (land) and 0 (water), and returns the number of islands. An island is a group of land squares connected up, down, left or right.

For example, ["01110", "01000", "00011", "11001"] returns 3: the shape in the top rows, the group on the right, and the pair in the bottom left corner.

Constraints: 1 <= number of rows, number of columns <= 150. All rows have the same length.