题目描述

给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

示例 2:

输入:

11000

11000

00100

00011

输出: 3

解题思路

深度优先遍历：每次遇到grid [i][j]==1 的地方，岛屿数+1，之后从该位置上下左右开始遍历，将遇到的1的位置全部置为0，遇到0的地方或者遍历返回。

代码示例

对每一个可能的元素(grid[i][j]==1)深入(上下左右方位)到不能再深入为止(一步步递归进行)，而且每个节点只能访问一次。

 func numIslands(grid [][]byte) int {
    var count int
    if len(grid) == 0{
        return count
    }
    rows := len(grid)
    cols := len(grid[0])

    for i := 0; i < rows; i++{
        for j := 0; j < cols; j++{
            if grid[i][j] == '1'{
                dfsHelper(grid, i, j, rows, cols)
                count++
            }
        }
    }

    return count
}

func dfsHelper(grid [][]byte, i, j, rows, cols int){
    if i < 0 || j < 0 || i >= rows || j >= cols || grid[i][j] == '0'{
        return
    }

    grid[i][j] = '0'
    dfsHelper(grid, i-1, j, rows, cols)
    dfsHelper(grid, i+1, j, rows, cols)
    dfsHelper(grid, i, j-1, rows, cols)
    dfsHelper(grid, i, j+1, rows, cols)

    return
}
  

如有不对、欢迎指正，相互学习，共同进步。