本文共 1538 字,大约阅读时间需要 5 分钟。
**题号: **200
**题目: **岛屿的个数 **难度: **中等 **内容: **给定一个由'1'
(陆地)和 '0'
(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 示例 1:
输入:11110110101100000000输出: 1
示例 2:
输入:11000110000010000011输出: 3
代码如下:
class Solution: def numIslands(self, grid): """ :type grid: List[List[str]] :rtype: int """ if len(grid) == 0: return 0 x = len(grid[0])-1 y = len(grid) -1 maxl = 0 #岛屿个数 for i in range(0,y+1): for p in range(0,x+1): now = grid[i][p] if now == "1": maxl = maxl + 1 l = [] l.append([i,p]) while len(l) != 0: nowi,nowp = l.pop() grid[nowi][nowp] = maxl #上 if nowi != 0: if grid[nowi-1][nowp] == "1": l.append([nowi-1,nowp]) #下 if nowi != y: if grid[nowi+1][nowp] == "1": l.append([nowi+1,nowp]) #左 if nowp != 0: if grid[nowi][nowp-1] == "1": l.append([nowi,nowp-1]) #右 if nowp != x: if grid[nowi][nowp+1] == "1": l.append([nowi,nowp+1]) return maxl
当然大家可以考虑用DFS做法!
转载地址:http://dvwpi.baihongyu.com/