理论基础

BFS和DFS是两种十分重要的搜索算法，BFS适合查找最优解，DFS适合查找是否存在解(或者说能找到任意一个可行解)。用这两种算法即可以解决大部分树和图的问题。**
广度遍历遍利用队列处理
深度遍历使用递归算法处理

代码示例

1是陆地 0是水
陆地通过水平与垂直方向连接
默认网格四周为水
求岛屿的数量

5 5
1 1 1 1 0
1 1 0 0 1
0 0 1 0 1
0 1 1 0 0
1 0 0 1 1

package main
import (
    "fmt"
    "os"
)

//读取网格
func readGrid(filename string) [][]int {
    file, err := os.Open(filename)
    if err != nil {
        panic(err)
    }
    var row, col int
    fmt.Fscanf(file, "%d %d",&row,&col)
    dfs := make([][]int,row)
    for i := range dfs {
        dfs[i] = make([]int,col)
        for j :=  range dfs[i] {
            fmt.Fscanf(file, "%d", &dfs[i][j])
        }
    }
    return dfs
}

//获取岛屿数量
func numIslands(grid [][]int) int {
    if grid == nil || len(grid) == 0 {
        return 0
    }
    num := 0
    for i := range gird {
        for j := range gird[i] {
            if grid[i][j] == 1 {
                num++
                dfs(grid, i, j)
            }
        }
    }
    return num
}

//深度遍历
func dfs(grid [][]int, i, j int) {
    row := len(gird)
    col := len(gird[0])
    if i < 0 || i>row || j<0 || j>col || gird[i][j] == 0 {
        return
    }
    gird[i][j] = '0'
    dfs(gird,i,j-1)
    dfs(grid,i-1,j)
    dfs(grid,i,j+1)
    dfs(grid,i+1,j)
}

func main() {
    grid := readGrid("dfs/dfs.in")
    num := numIslands(grid)
    fmt.Println(num)
}