岛屿数量

题目描述

https://leetcode-cn.com/problems/number-of-islands/

解

package main

// 深度优先遍历
func numIslands(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }
    var r int
    // 遍历每个点 只向下和向右遍历
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            // 改点是岛屿 并且曾经没去过
            if grid[i][j] != '1' {
                continue
            }
            DFS2(i, j, grid)
            r++
        }
    }
    return r
}

func DFS2(x int, y int, grid [][]byte) {
    // 边界条件
    if x < 0 || y < 0 || x >= len(grid) || y >= len(grid[0]) {
        return
    }
    if grid[x][y] == '0' {
        return
    }
    grid[x][y] = '2'
    //  只有满足两个条件才处理，减少重复递归
    if x+1 < len(grid) && grid[x+1][y] == '1' {
        DFS2(x+1, y, grid)
    }
    if x-1 >= 0 && grid[x-1][y] == '1' {
        DFS2(x-1, y, grid)
    }
    if y+1 < len(grid[0]) && grid[x][y+1] == '1' {
        DFS2(x, y+1, grid)
    }
    if y-1 >= 0 && grid[x][y-1] == '1' {
        DFS2(x, y-1, grid)
    }
}

思路

这道题使用了深度优先遍历，当然广度优先遍历也是可以的，最后看题解有并查集的算法，这个可以了解下。