Problem

Given a 2D grid grid of characters where each cell is either '1' (land) or '0' (water), return the number of islands. An island is a group of horizontally or vertically adjacent land cells, and the grid is surrounded by water.

Examples

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: 1
Explanation: All land cells are connected into one island.

Example 2:

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 groups of connected land.

Constraints

• 1 <= rows, cols <= 300
• grid[i][j] is either '0' or '1'
• Cells are connected only in 4 directions: up, down, left, and right