Given a 2D grid map of '1' s (land) and '0' s (water), write a program to count the number of islands.

Problem Note

  • You may assume all four edges of the grid are all surrounded by water.
  • A group of connected 1s forms an island. For example, the below matrix contains 5 islands

Example 1

Input: grid[][] = [ 
                 [1, 1, 0, 0, 0],
                 [0, 1, 0, 0, 1],
                 [0, 0, 0, 1, 1],
                 [0, 0, 0, 0, 0],
                 [1, 1, 1, 0, 1]
                ]           
Output: 4

Example 2

Input: grid[][] = [ 
                 [1, 1, 0, 0, 0],
                 [0, 0, 1, 0, 1],
                 [0, 0, 0, 1, 1],
                 [0, 0, 0, 0, 1],
                 [1, 1, 1, 0, 1]
                ]                 
Output: 2