Graph Island Count

Problem: Graph Island Count

On January 25, as we celebrate new beginnings and connections, your task is to count the number of distinct islands in a grid. An island is made up of adjacent land cells (represented by '1') connected horizontally or vertically. Water is represented by '0'.

Task

Given a 2D grid of characters, write a function that returns the number of islands. Two cells belong to the same island if they are both '1' and are connected horizontally or vertically.

Example

Input:

[
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"]
]

Output: 3

Constraints

• The grid dimensions can be assumed to be at most 300x300.
• You can assume that all four edges of the grid are surrounded by water ('0').
• Try to aim for a time complexity near O(m*n), where m and n are the dimensions of the grid.

Starter Code

Below is some starter code in multiple languages to help you begin your solution.