Problem Description

Given an m x n 2D binary grid 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. You may assume all four edges of the grid are all 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

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:

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

解析

給定一個 2 D 二元矩陣 grid ， 每個元素 grid[r][c] 只有 1 或是 0 兩種值

1 代表是陸地，0 代表是 水

如果水平或是垂直相鄰位置都是 1 代表 cell屬於同一個 island

題目實作一個演算法從 grid 找出總共有幾個 island

直覺去思考，可以發現要找出有幾個 island 代表要去找有幾個相連的區塊