前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >DFS&BFS - 200. Number of Islands

DFS&BFS - 200. Number of Islands

作者头像
ppxai
发布2020-09-23 17:31:59
4300
发布2020-09-23 17:31:59
举报
文章被收录于专栏:皮皮星球

200. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

代码语言:javascript
复制
Input:
11110
11010
11000
00000

Output: 1

Example 2:

代码语言:javascript
复制
Input:
11000
11000
00100
00011

Output: 3

思路:

题目意思是在一个二维平面找出有多少个岛屿,可以使用dfs或者bfs做,这里使用dfs来做,每找到一个点是岛屿,就不断四个方向探索,把探索过的区域打上标记或者置为水域就可以。

代码:

go:

代码语言:javascript
复制
var dirs = [][]int{{-1, 0},{1, 0}, {0, -1}, {0, 1}}


func numIslands(grid [][]byte) int {
    var res int
    //sanity check
    if grid == nil || len(grid) == 0 || len(grid[0]) == 0 {
        return res
    }
    
    row, col := len(grid), len(grid[0])
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            if grid[i][j] == '1' {
                res++
                dfs(&grid, i, j, row, col)
            }
        }
    }
    
    return res
}

func dfs(grid *[][]byte, x, y int, row, col int) {
    // base case
    if x < 0 || x >= row || y < 0 || y >= col || (*grid)[x][y] == '0' || (*grid)[x][y] == '2' {
        return 
    }
    
    (*grid)[x][y] = '2'
    for _, dir := range dirs {
        dfs(grid, dir[0] + x, dir[1] + y, row, col)
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年09月18日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档