使用 Python 计算所有正方形子矩阵数量的程序

假设我们有 mxn 二进制矩阵，我们必须找出有多少个方阵都是 1。

所以，如果输入就好了。

那么输出将是 15，因为边 1 有 10 个正方形。边 2 有 4 个正方形，边 3 有 1 个正方形。那么正方形的总数 = 10 + 4 + 1 = 15。

为了解决这个问题，我们将按照以下步骤操作 -

• 如果矩阵只有一个，那么

• 返回 1

• rows := 矩阵的行数

• cols := 矩阵的列数[0]

• 结果：= 0

• 对于范围 0 到行 - 1 中的行，请执行

• 如果 row 与 0 相同或 col 与 0 相同，则

• square := 1 +（矩阵[row-1,col]、矩阵[row,col-1]和矩阵[row-1,col-1]的最小值）

• 矩阵[行，列] := 正方形

• 结果 := 结果 + 平方

• 结果 := 结果 + 1

• 如果 matrix[row, col] 与 1 相同，则

• 否则当 matrix[row, col] 与 1 相同时，则

• 对于 0 到 cols - 1 范围内的 col，执行

• 返回结果

让我们看看以下实现以获得更好的理解 -

示例

def solve(matrix):
   if matrix == [[1]]:
      return 1
   rows = len(matrix)
   cols = len(matrix[0])
   result = 0
   for row in range(rows):
      for col in range(cols):
         if (row == 0 or col == 0):
            if matrix[row][col] == 1:
               result += 1
         elif matrix[row][col] == 1:
            square = min(matrix[row-1][col], min(matrix[row][col-1], matrix[row-1][col-1])) + 1
            matrix[row][col] = square
            result += square
   return result
matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
print(solve(matrix))

输入

{{0,1,1,1},{1,1,1,1},{0,1,1,1}}

15