在Python中删除所有被水完全包围的岛屿的程序
假设我们有一个二进制矩阵,其中1表示陆地,0表示水。 岛屿是由0(水)或边界包围的1组。 我们必须找到完全由水环绕的所有岛屿,并将它们修改为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:一个新的集合
-
对于i在范围0到row中,
- 对于j在范围0到col中,
- 如果i和j不在矩阵范围内,则
-
进入下一个迭代
-
如果(i,j)被看到,则
-
进入下一个迭代
-
如果 A [i,j]与0相同,则
-
进入下一个迭代
-
d:具有一个元素(i,j)的双端队列
-
while d不为空,执行以下操作
-
(x,y):d的左侧元素,并从d中删除
-
B [x,y] = 1
-
对于(x,y)的每个邻居(x2,y2),执行以下操作
- 如果(x2,y2)未被看到,则
-
在d的末尾插入(x2,y2)
-
标记(x2,y2)为seen
- 对于j在范围0到col中,
-
返回B
更多Python相关文章,请阅读:Python 教程
例子
让我们看下面的实现,以更好地理解 –
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]
]