岛屿数量

1. 题目描述

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

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

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

2. 思路

1. 思路一
   • DFS
   • 只要遇到'1'那么上下左右穷举能达到的坐标
   • 使用set记录已访问过的(i,j)

3. 实现

3.1. DFS

func numIslands(grid [][]byte) int {
    maxRow := len(grid)
    maxCol := len(grid[0])
    visited := make([][]bool, maxRow)
    for i:=0; i < len(visited);i++{
        visited[i] = make([]bool, maxCol)
    }

    count := 0
    for i := range grid {
        for j := range grid[i] {
            if !visited[i][j] && grid[i][j] == '1' {
                visitIsland(grid, i, j, maxRow, maxCol, visited)
                count++
            }
        }
    }
    return count
}

func visitIsland(grid [][]byte, row, col, maxRow, maxCol int, visited [][]bool) {
    if row < 0 || row >= maxRow || col < 0 || col >= maxCol {
        return
    }

    if grid[row][col] == '0' {
        return 
    }

    if visited[row][col] {
        return
    }

    visited[row][col] = true
    visitIsland(grid, row+1, col, maxRow, maxCol, visited)
    visitIsland(grid, row-1, col, maxRow, maxCol, visited)
    visitIsland(grid, row, col+1, maxRow, maxCol, visited)
    visitIsland(grid, row, col-1, maxRow, maxCol, visited)
}

4. 参考

• 200. 岛屿数量 - 力扣（LeetCode）