在Python中统计给定二进制矩阵中正方形子矩阵的数量

在Python中统计给定二进制矩阵中正方形子矩阵的数量

假设我们有一个二维二进制矩阵。我们必须查找矩阵中出现的所有元素都为1的正方形子矩阵的总数。

因此,如果输入是这样的:

0 1 1
0 1 1

那么输出将为5,因为有一个(2 x 2)正方形和四个(1 x 1)正方形。

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

  • 如果mat为空,则
    • 返回0
  • c := 0
  • 对于i在mat的行数上从0到循环,执行以下操作 –
    • 对于j在mat的列数上从0到循环,执行以下操作-
      • 如果mat[i, j]是1,则
      • 如果i为0或j为0,则
        • c := c + 1
      • 否则,
        • temp =(min(mat[i-1,j-1],mat[i,j-1]和mat[i-1,j])+ mat[i,j]
        • c := c + temp
        • mat[i,j] := temp
  • 返回c

示例

让我们看下面的实现,以便更好地理解 –

def solve(mat):
   if mat == []:
      return 0
   c = 0

   for i in range(len(mat)):
      for j in range(len(mat[0])):
         if mat[i][j] == 1:
            if i == 0 or j == 0:
               c += 1
            else:
               temp = (min(mat[i - 1][j - 1], mat[i][j - 1], mat[i - 1][j]) + mat[i][j])
               c += temp
               mat[i][j] = temp
   return c

matrix = [
   [0, 1, 1],
   [0, 1, 1]
]
print(solve(matrix))

输入

[[2, 6],[3, 4],[4, 7],[5, 5]]

输出

5

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程