Number of Islands

Given an m x n grid where 1 represents land and 0 represents water, return the number of islands.

An island is a group of 1s connected horizontally or vertically (not diagonally), surrounded by water. You may assume all four edges of the grid are surrounded by water.

You are allowed to modify the grid.

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

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

Constraints

• 1 <= m, n <= 100
• grid[i][j] is 0 or 1.