岛屿数量

题目描述：

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

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

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

示例 1：

输入：grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
输出：1
示例 2：

输入：grid = [
[“1”,”1”,”0”,”0”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”1”,”0”,”0”],
[“0”,”0”,”0”,”1”,”1”]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

思路:

经典的dfs题，第一次到达就把flag置1，碰到一次下一次就不再重复碰

代码:

func numIslands(grid [][]byte) int {
    var flag [][]int
    if len(grid) == 0{
        return 0
    }
    var count int
    var move  =[]int{0,1,1,0,-1,0,0,-1}
    m,n := len(grid), len(grid[0])
    flag = make([][]int, len(grid))
    for i:=0;i < m;i++{
        flag[i] = make([]int, n)
    }
    var dfs func(i,j int)
    
    dfs = func(i,j int){
        if flag[i][j] == 1 || grid[i][j] == '0'{
            return 
        }
        flag[i][j] = 1
        for k:=0;k<4;k++{
            x,y := move[k*2] + i,move[k*2 +1] + j
            if x >= 0 && x <m && y >= 0 && y < n && flag[x][y] == 0 && grid[x][y] == '1'{
               
                dfs(x,y)
            }  
        }
    }

    for i:=0;i<m;i++{
        for j:=0;j <n; j++{
            if grid[i][j] == '1' && flag[i][j] == 0{
                count ++
                dfs(i,j)
                
            }
        }
    }
    return count
}

代码效率：

执行用时：4 ms, 在所有 Go 提交中击败了93.21%的用户
内存消耗：5.1 MB, 在所有 Go 提交中击败了23.18%的用户