分享
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
# go 图的深度遍历 leetcode 200
[leetcode 200岛屿数量](https://leetcode-cn.com/problems/number-of-islands/)
## 使用dfs遍历图,要注意两点
1. dfs要有结束的出口
2. 要找到当前结点的所有子节点
其他的优化就是各种减枝
## code
连通图,将矩阵中的每一个点都看作图的一个节点,只有两个节点的value相同且相邻,这两个节点才是相连的
```go
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)
}
}
}
}
```
有疑问加站长微信联系(非本文作者))
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1128 次点击
上一篇:Go 1.17泛型尝鲜
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传