用Python查找所有具有1的正方形子矩阵的数量

假设我们有一个二维二进制矩阵，我们需要找到所有包含 1 的正方形子矩阵的总数。

所以，如果输入是这样的：

1	1	1	0
1	1	1	0
1	1	1	0
0	0	0	0
1	0	1	1

那么输出将为17，因为有12个（1 x 1）的正方形、4个（2 x 2）的正方形和1个（3 x 3）的正方形。

为了解决这个问题，我们需要进行以下步骤：

• res := 0
• for i in range 0 to matrix 的行数, do
  • for j in range 0 to matrix 的列数, do
    • if i is same as 0 or j is same as 0, then
    • res := res + matrix[i, j]
    • otherwise when matrix[i, j] is same as 1, then
    • matrix[i, j] = (matrix[i, j – 1]、matrix[i – 1, j] 和 matrix[i – 1, j – 1]）的最小值 + 1
    • res := res + matrix[i, j]
• return res

看下面的实现代码可以更好地理解这个过程。

更多Python相关文章，请阅读：Python 教程

实现例子

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