在Python中从给定矩阵中查找不同岛屿的数量
假设我们有一个2D二进制矩阵,我们需要找出给定矩阵中不同岛屿的数量。其中1表示陆地,0表示水域,因此一个岛屿是由靠近且周长被水包围的一组1组成的。如果两个岛屿的形状不同,则它们是唯一的两个岛屿。
因此,如果输入如下:
1 | 0 | 0 | 0 | 0 |
---|---|---|---|---|
1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 1 |
0 | 0 | 1 | 0 | 0 |
1 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 1 | 1 |
那么输出将会是4(不同颜色表示不同的岛屿)。
要解决这个问题,我们将采取以下步骤−
- 定义一个函数dfs()。这将接受i,j,k,l四个变量。
-
mat[i,j]:=0
-
在形状的末尾插入(i−k,j−l)这对坐标
-
如果i+1 < mat的行数且mat [i + 1,j]为1,则
- dfs(i + 1, j, k, l)
- 如果j + 1 < mat的列数且mat [i,j + 1]为1,则
- dfs(i, j + 1, k, l)
- 如果i−1> = 0且mat [i − 1,j]为1,则
- dfs(i − 1,j,k,l)
- 如果j−1> = 0且mat [i,j − 1]为1,则
- dfs(i,j − 1,k,l)
- 从主方法执行以下操作−
-
cnt:= 0
-
shapes:=一个新的集合
-
对于i in range 0 to mat的行数,进行以下操作
- 对于j in range 0 to mat的列数,进行以下操作
- 如果mat [i,j]为1,则
-
shape:=一个新的列表
-
dfs(i,j,i,j)
-
如果形状不在形状集中,则
- cnt:=cnt + 1
- 将形状插入到形状集中
- 对于j in range 0 to mat的列数,进行以下操作
-
返回cnt
让我们看下面的实现以更好地理解−
更多Python相关文章,请阅读:Python 教程
示例
class Solution:
def solve(self, mat):
def dfs(i, j, k, l):
mat[i][j] = 0
shape.append((i − k, j − l))
if i + 1 < len(mat) and mat[i + 1][j]:
dfs(i + 1, j, k, l)
if j + 1 < len(mat[0]) and mat[i][j + 1]:
dfs(i, j + 1, k, l)
if i − 1 >= 0 and mat[i − 1][j]:
dfs(i − 1, j, k, l)
if j − 1 >= 0 and mat[i][j − 1]:
dfs(i, j − 1, k, l)
cnt = 0
shapes = set()
for i in range(len(mat)):
for j in range(len(mat[0])):
if mat[i][j]:
shape = []
dfs(i, j, i, j)
shape = tuple(shape)
if shape not in shapes:
cnt += 1
shapes.add(shape)
return cnt
ob = Solution()
matrix = [
[1, 0, 0, 0, 0],
[1, 0, 1, 0, 1],
[0, 1, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0],
[1, 1, 0, 1, 1]
]
print(ob.solve(matrix))
输入
[
[1, 0, 0, 0, 0],
[1, 0, 1, 0, 1],
[0, 1, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0],
[1, 1, 0, 1, 1]
]
输出
4