理论基础
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)
}