+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2019-04(1)

2019-06(2)

2019-07(2)

2019-08(87)

2019-09(90)

leetcode 200. 岛屿数量

发布于2020-08-01 21:14     阅读(339)     评论(0)     点赞(19)     收藏(1)


给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。


示例 1:

输入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。


DFS

  1. class Solution(object):
  2. def numIslands(self, grid):
  3. """
  4. :type grid: List[List[str]]
  5. :rtype: int
  6. """
  7. if not grid:
  8. return 0
  9. height = len(grid)
  10. width = len(grid[0])
  11. count = 0
  12. for i in range(height):
  13. for j in range(width):
  14. if grid[i][j] == '1':
  15. count += 1
  16. self.isLand(grid,i,j)
  17. return count
  18. def isLand(self, grid, i, j):
  19. height = len(grid)
  20. width = len(grid[0])
  21. grid[i][j] = '0'
  22. if i-1 >= 0 and grid[i-1][j] == '1':
  23. self.isLand(grid,i-1,j)
  24. if i+1 < height and grid[i+1][j] == '1':
  25. self.isLand(grid,i+1,j)
  26. if j-1 >= 0 and grid[i][j-1] == '1':
  27. self.isLand(grid,i,j-1)
  28. if j+1 < width and grid[i][j+1] == '1':
  29. self.isLand(grid,i,j+1)

遍历二维数组,当出现1时就从该点出发开始扩散,并把所有能到达的地方标为0。最后只需要统计进行了几次函数调用即可。

BFS

  1. class Solution:
  2. def numIslands(self, grid: List[List[str]]) -> int:
  3. nr = len(grid)
  4. if nr == 0:
  5. return 0
  6. nc = len(grid[0])
  7. num_islands = 0
  8. for r in range(nr):
  9. for c in range(nc):
  10. if grid[r][c] == "1":
  11. num_islands += 1
  12. grid[r][c] = "0"
  13. neighbors = collections.deque([(r, c)])
  14. while neighbors:
  15. row, col = neighbors.popleft()
  16. for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
  17. if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
  18. neighbors.append((x, y))
  19. grid[x][y] = "0"
  20. return num_islands

既然可以使用深度优先搜索,那么必然可以使用BFS来代替。我们在这里加入一个队列表示待处理的邻居。为了求出岛屿的数量,我们可以扫描整个二维网格。如果搜到一个为1的格子,那么便将其标为0,并将其加入队列。每一个邻居都会被标为0并且被加入到队列中。最后直到队列为空,扫描邻居结束。最后我们记录得到的岛屿数量即为我们进行广度优先搜索的次数。

原文链接:https://blog.csdn.net/qq_41662990/article/details/107680000



所属网站分类: 技术文章 > 博客

作者:智慧星辰

链接: https://www.pythonheidong.com/blog/article/468798/

来源: python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

19 0
收藏该文
已收藏

评论内容:(最多支持255个字符)