Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1Example 2:
Input: grid = [["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3This problem is a classic connected-components count on a grid. Scan each cell, and whenever you find a land cell ('1'), increment the island count and use DFS or BFS to mark all four-directionally connected land cells as visited. This prevents double counting and yields an O(mn) solution, which is efficient enough for the given grid size.
END
