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.
grid = [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]Output3WhyThe top-left block, the middle single land cell, and the bottom-right pair form three separate islands.grid = [['1','1','1'],['0','1','0'],['1','1','1']]Output1WhyAll land cells are connected through vertical and horizontal paths, so they form one island.grid = [['0','0'],['0','0']]Output0WhyThere is no land in the grid, so no islands exist.1 <= len(grid) <= 3001 <= len(grid[0]) <= 300grid[i][j] is either '0' or '1'Cells are connected only in 4 directions: up, down, left, rightYou may modify the input grid in placedef num_islands(grid):