程序从Python中的给定矩阵中查找许多不同的岛形
假设我们有一个二维二进制矩阵，我们必须找到给定矩阵中不同岛的数量。这里1代表土地，0代表水，因此一个岛是一组1s，它们很近且周围被水包围。如果两个岛的形状不同，则此处是唯一的。
所以，如果输入像
那么输出将为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
形状：=新套
对于0到行数范围内的i，执行
如果mat[i，j]为1，则
cnt：=cnt+1
形状：=一个新列表
dfs(i,j,i,j)
如果形状不是形状，则
将形状插入形状
对于范围为0到垫子的列数的j，执行
返回cnt
让我们看下面的实现以更好地理解-
示例
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