在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
    • 将形状插入到形状集中

• 返回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