程序从Python中的给定矩阵中查找许多不同的岛形

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个二维二进制矩阵，我们必须找到给定矩阵中不同岛的数量。这里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

以上是 程序从Python中的给定矩阵中查找许多不同的岛形 的全部内容， 来源链接： utcz.com/z/350127.html