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.
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.
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.
1 <= len(grid) <= 3001 <= len(grid[0]) <= 300grid[i][j] is either '0' or '1'A correct solution should avoid recounting cells that already belong to a discovered island.