Count Islands

You are given a 2D grid of '1's (land) and '0's (water). An island is a group of '1's connected horizontally or vertically (not diagonally). Assume all four edges of the grid are surrounded by water. Return the number of islands.

Example 1

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3 (the top-left 2x2 block, the single cell at (2,2), and the bottom-right pair).

Example 2

grid = [
  ["1","1","1"],
  ["0","1","0"],
  ["1","1","1"]
]

Output: 1 (every land cell is connected into one shape).

Constraints

• 1 <= rows, cols <= 300
• grid[i][j] is either '0' or '1'.