Python 中查找具有 1 的正方形子矩阵数量的程序

假设我们有一个 2D 二进制矩阵，我们需要找到其中等于 1 的正方形子矩阵的总数量。

所以，如果输入如下

那么输出将是 17，因为有 12 个 (1 x 1) 正方形、4 个 (2 x 2) 正方形和 1 个 (3 x 3) 正方形。

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

• res := 0
• 对于 0 到矩阵行数范围内的 i，执行
  • 对于 0 到矩阵列数范围内的 j，执行
    • 如果 i 等于 0 或 j 等于 0，那么
      • res := res + matrix[i, j]
    • 否则，当 matrix[i, j] 等于 1 时，那么
      • matrix[i, j] = minimum of (matrix[i, j - 1], matrix[i - 1, j] and matrix[i - 1, j - 1]) + 1
      • res := res + matrix[i, j]
• 返回 res

我们来看一下以下实现以获得更好的理解 −

示例 

在线演示

class Solution:
   def solve(self, matrix):
      res = 0
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if i == 0 or j == 0:
               res += matrix[i][j]
            elif matrix[i][j] == 1:
               matrix[i][j] = min(matrix[i][j - 1], matrix[i - 1][j], matrix[i - 1][j - 1]) + 1
               res += matrix[i][j]
      return res

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

输入

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

输出

17

Arnab Chakraborty

更新于： 02-12-2020

96 次浏览

开启你的职业生涯

通过完成课程来获得认证

开始