Description
Given an m x n 2D binary grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Examples
Input:
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]Output:
1Explanation:
One connected island of 1s.
Input:
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]Output:
3Explanation:
Three separate islands.
Input:
grid = [["0","1","0","1","0"],["1","0","1","0","1"],["0","1","0","1","0"],["1","0","1","0","1"]]Output:
8Explanation:
This checkerboard pattern creates 8 separate single-cell islands since no two adjacent cells (horizontally or vertically) contain '1's that can connect to form larger islands.
Constraints
- •
m == grid.length - •
n == grid[i].length - •
1 ≤ m, n ≤ 300 - •
grid[i][j] is '0' or '1'.