首页 > 其他 > 详细

岛屿数量

时间:2021-05-27 11:05:41      阅读:21      评论:0      收藏:0      [点我收藏+]

问题:

# 给你一个由 ‘1‘(陆地)和 ‘0‘(水)组成的的二维网格,请你计算网格中岛屿的数量。 
#
# 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
#
# 此外,你可以假设该网格的四条边均被水包围。
#
#
#
# 示例 1:
#
#
# 输入:grid = [
# ["1","1","1","1","0"],
# ["1","1","0","1","0"],
# ["1","1","0","0","0"],
# ["0","0","0","0","0"]
# ]
# 输出:1

方法:dfs,bfs,并查集

# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0

        def dfs(i, j):
            # 数据抹零
            grid[i][j] = 0
            # 查找上下左右
            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                x, y = i + dx, j + dy
                if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                    dfs(x, y)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    count += 1
                    dfs(i, j)
        return count
# leetcode submit region end(Prohibit modification and deletion)

 

岛屿数量

原文:https://www.cnblogs.com/demo-deng/p/14815505.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!