题目： 岛屿计算
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例.png
解题思路：
首先明白岛屿的定义：一块 1 周围全是 0，即为一个岛屿。（注意：grid 数组内的 1、0 均为char型字符，非整型）
示例1 中所有 1 都可以连接到一起，即所有 1 组成一个岛屿。示例2 中的三个岛屿：左上角四个1、中间一个1、右下角一个一，分别组成三个岛屿。
Flood fill算法是从一个区域中提取若干个连通的点与其他相邻区域区分开（或分别染成不同颜色）的经典算法。因为其思路类似洪水从一个区域扩散到所有能到达的区域而得名。在 GNU Go 和 扫雷 中，Flood Fill算法被用来计算需要被清除的区域。由上述定义可看出该题是典型的Flood fill算法类型例题，将岛屿与水分开，并染成特定颜色，以记录已累加过该岛屿。
每块岛屿可以看成相连的一个个节点，只需把所有相连节点遍历殆尽并标上特殊值以记录该节点已访问过，则遍历殆尽时证明一块岛屿已找到。
方法一： 广度优先
class Solution:
def numIslands(self, grid: list) -> int:
if not grid or len(grid) == 0:
return 0
row, colum = len(grid), len(grid[0])
# 岛屿计数
island_num = 0
for i in range(row):
for j in range(colum):
if grid[i][j] == '1':
self.bfs(grid, i, j, row, colum)
# 遍历一次计数加一，直到结束
island_num += 1
return island_num
def bfs(self, grid: list, i: int, j:int, row: int, colum: int):
queue = list()
queue.append((i, j))
while queue:
a, b = queue.pop(0)
# 上方判断
if a - 1 >= 0 and grid[a - 1][b] == '1':
queue.append((a - 1, b))
grid[a - 1][b] = '0'
# 下方判断
if a + 1 < row and grid[a + 1][b] == '1':
queue.append((a + 1, b))
grid[a + 1][b] = '0'
# 左边判断
if b - 1 >= 0 and grid[a][b - 1] == '1':
queue.append((a, b - 1))
grid[a][b - 1] = '0'
# 右边判断
if b + 1 < colum and grid[a][b + 1] == '1':
queue.append((a, b + 1))
grid[a][b + 1] = '0'
if __name__ == '__main__':
grid = [
["1", "1", "0", "0", "1"],
["1", "1", "0", "1", "0"],
["0", "0", "1", "0", "0"],
["1", "0", "0", "1", "1"]
]
S = Solution()
num = S.numIslands(grid)
print(num)
>>> 6
方法二：深度优先
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid or len(grid) == 'o': return 0
row, columns = len(grid), len(grid[0])
count = 0
for i in range(row):
for j in range(columns):
if grid[i][j] == '1':
self.dfs(grid, i, j, row, columns)
count += 1
return count
def dfs(self, grid: List[List[str]], i: int, j: int, row: int, columns: int):
if i >= row or i < 0 or j >= columns or j < 0 or grid[i][j] == '0': return
grid[i][j] = '0'
self.dfs(grid, i - 1, j, row, columns)
self.dfs(grid, i, j - 1, row, columns)
self.dfs(grid, i + 1, j, row, columns)
self.dfs(grid, i, j + 1, row, columns)
···
网友评论