在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))