go 图的深度遍历 leetcode 200

letterbeezps · · 753 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

# 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

753 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传