力扣-200.岛屿的数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

解题思路

采用递归的方式，首先遍历数组元素。当遇到1时，将该元素赋值为0，当该元素上下左右四个方向有元素为1时，则继续递归，递归结束证明该岛屿所有板块找到，数量+1，继续遍历。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var numIslands = function(grid) {
    function recursion(i,j){
        // 将该元素置0
        grid[i][j] = 0
        // 上下左右四个方向有元素为1时，则继续递归
        if(i+1<m && grid[i+1][j]==1) recursion(i+1,j)
        if(i-1>=0 && grid[i-1][j]==1) recursion(i-1,j)
        if(j+1<n && grid[i][j+1]==1) recursion(i,j+1)
        if(j-1>=0 && grid[i][j-1]==1) recursion(i,j-1)
    }
    let m = grid.length
    let n = grid[0].length
    //记录岛屿数量
    let cnt = 0
    //遍历数组元素
    for(let i = 0;i < m;i ++){
        for(let j = 0;j < n;j ++){
            //当遇到1时执行递归
            if(grid[i][j] == 1){
                recursion(i,j)
                // 递归结束，岛的数量+1
                cnt++
            }
        }
    }
    return cnt
};