数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序移除完全被水包围的岛屿
假设我们有一个二进制矩阵，其中 1 表示陆地，0 表示水。一个岛屿是由 1 组成的，并且被 0（水）或边缘包围。我们需要找到所有完全被水包围的岛屿，并将它们修改为 0。我们知道，如果一个岛屿的所有邻居（水平和垂直，而非对角线）都是 0（没有邻居是边缘），则该岛屿被完全包围。
因此，如果输入如下所示：
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 1 |
则输出将是
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 |
为了解决这个问题，我们将遵循以下步骤：
row := A 的行数
col := A 的列数
B := 一个与 A 大小相同且填充为 0 的矩阵
seen := 一个新的集合
对于范围从 0 到 row 的 i，执行：
对于范围从 0 到 col 的 j，执行：
如果 i 和 j 超出矩阵范围，则
进行下一次迭代
如果 (i, j) 已经被访问过，则
进行下一次迭代
如果 A[i, j] 等于 0，则
进行下一次迭代
d := 一个双端队列，包含一个元素 (i, j)
当 d 不为空时，执行：
(x, y) := d 的左侧元素，并从 d 中删除
B[x, y] := 1
对于 (x, y) 的每个邻居 (x2, y2)，执行：
如果 (x2, y2) 没有被访问过，则
将 (x2, y2) 插入到 d 的末尾
标记 (x2, y2) 为已访问
返回 B
示例
让我们看看以下实现，以便更好地理解：
from collections import deque class Solution: def solve(self, A): row = len(A) col = len(A[0]) B = [[0 for _ in range(col)] for _ in range(row)] seen = set() def nei(i, j): if i + 1 < row and A[i + 1][j]: yield (i + 1, j) if j + 1 < col and A[i][j + 1]: yield (i, j + 1) if i - 1 >= 0 and A[i - 1][j]: yield (i - 1, j) if j - 1 >= 0 and A[i][j - 1]: yield (i, j - 1) for i in range(row): for j in range(col): if i not in (0, row - 1) and j not in (0, col - 1): continue if (i, j) in seen: continue if A[i][j] == 0: continue d = deque([(i, j)]) while d: x, y = d.popleft() B[x][y] = 1 for x2, y2 in nei(x, y): if (x2, y2) not in seen: d.append((x2, y2)) seen.add((x2, y2)) return B ob = Solution() matrix = [ [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1], ] print(ob.solve(matrix))
输入
[ [1, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 1], ]
输出
[ [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1] ]
更新于: 2020年12月22日
635 次浏览
广告