在Python中编写程序以计算矩阵中被环绕岛屿的数量

在Python中编写程序以计算矩阵中被环绕岛屿的数量

假设我们有一个二进制矩阵。其中1表示陆地,0表示水。正如我们所知,一个岛屿是由聚在一起的1组成的,其周长被水包围。我们必须找到完全被包围的岛屿的数量。

因此,如果输入如下所示:

在Python中编写程序以计算矩阵中被环绕岛屿的数量

那么输出将为2,因为有三个岛屿,但其中两个被完全包围。

为了解决这个问题,我们将遵循以下步骤 −

  • 定义一个函数dfs()。它将会带参数i,j
  • 如果i和j不在矩阵的范围内,那么
    • 返回False
  • 如果矩阵[i,j]与0相同,那么
    • 返回True
  • 矩阵[i,j]:= 0
  • a:= dfs(i + 1,j)
  • b:= dfs(i – 1,j)
  • c:= dfs(i,j + 1)
  • d:= dfs(i,j – 1)
  • 返回a和b和c和d
  • 从主方法执行以下操作:
  • R:=矩阵的行数,C:=矩阵的列数
  • 答案:= 0
  • 对于范围在0到R的i,做以下操作:
    • 对于范围在0到C的j,做以下操作:
      • 如果矩阵[i,j]与1相同,那么
      • 如果dfs(i,j)为真,则
        • 答案:=答案+1
  • 返回答案

看下面的实现以更好地理解−

更多Python相关文章,请阅读:Python 教程

样例

class Solution:
   def solve(self, matrix):
      def dfs(i, j):
         if i < 0 or j < 0 or i >= R or j >= C:
            return False
         if matrix[i][j] == 0:
            return True
         matrix[i][j] = 0
         a = dfs(i + 1, j)
         b = dfs(i - 1, j)
         c = dfs(i, j + 1)
         d = dfs(i, j - 1)
         return a and b and c and d

      R, C = len(matrix), len(matrix[0])
      ans = 0
      for i in range(R):
         for j in range(C):
            if matrix[i][j] == 1:
               if dfs(i, j):
                  ans += 1
      return ans

ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [0, 0, 0, 1, 0],
   [0, 1, 0, 0, 0],
   [0, 1, 0, 0, 0],
   [0, 1, 1, 1, 0],
   [0, 0, 0, 0, 0]
]
print(ob.solve(matrix))

输入

matrix = [  
[1, 0, 0, 0, 0],  
[0, 0, 0, 1, 0],  
[0, 1, 0, 0, 0],  
[0, 1, 0, 0, 0],  
[0, 1, 1, 1, 0],  
[0, 0, 0, 0, 0] ]

输出

2

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程