在Python中从给定矩阵中查找不同岛屿的数量

在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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程