5
go 图的深度遍历 leetcode 200
source link: https://studygolang.com/articles/35295
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
go 图的深度遍历 leetcode 200
使用dfs遍历图，要注意两点
- dfs要有结束的出口
- 要找到当前结点的所有子节点
其他的优化就是各种减枝
连通图，将矩阵中的每一个点都看作图的一个节点，只有两个节点的value相同且相邻，这两个节点才是相连的
var row = 0
var col = 0
var d = [][]int{
{-1, 0},
{0, 1},
{1, 0},
{0, -1},
}
func numIslands(grid [][]byte) int {
res := 0
if len(grid) == 0 || len(grid[0]) == 0 {
return 0
}
row = len(grid)
col = len(grid[0])
// 初始化参数完毕，
for i :=0; i<row; i++ {
for j := 0; j<col; j++ {
// 减少不必要的dfs
if grid[i][j] == '1' {
res ++
dfs(grid, i, j)
}
}
}
return res
}
// dfs
func dfs (grid [][]byte, x, y int) {
grid[x][y] = '0'
// 潜在的4个子节点
for i:=0; i<4; i++ {
newx := x+d[i][0]
newy := y+d[i][1]
// 出去出界的坐标
if newx >= 0 && newx < row && newy >=0 && newy < col {
// 只要岛屿，'0'就不考虑了
if grid[newx][newy] == '1' {
dfs(grid, newx, newy)
}
}
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK