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

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

所以，如果输入如下：

011
011

那么输出将是5，因为有一个(2 × 2)的正方形和四个(1 × 1)的正方形。

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

  • 如果mat为空，则
    • 返回0
  • c := 0
  • 对于i从0到mat的行数，执行：
    • 对于j从0到mat的列数，执行：
      • 如果mat[i, j]为1，则
        • 如果i为0或j为0，则
          • c := c + 1
        • 否则，
          • temp = (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

更新于：2021年10月18日

392 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告