Problem

In a simplified Meta Messenger map, a 2D grid represents water and land, where '1' is land and '0' is water. Count how many distinct islands exist.

An island is a group of horizontally or vertically adjacent land cells. Cells connected diagonally do not belong to the same island.

Formal Specification

Write a function that takes grid, a list of lists of single-character strings ('0' or '1'), and returns an integer: the number of islands.

Examples

Example 1

Input: grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
Output: 3

Explanation: There are three separate land masses.

Example 2

Input: grid = [
  ['1','1','1'],
  ['0','1','0'],
  ['1','1','1']
]
Output: 1

Explanation: All land cells are connected through horizontal or vertical neighbors.

Constraints

• 1 <= len(grid) <= 300
• 1 <= len(grid[0]) <= 300
• grid[i][j] is either '0' or '1'
• You may modify the input grid in place

A correct solution should avoid recounting cells that already belong to a discovered island.