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

示例

让我们看看下面的实现,以便更好地理解:

Open Compiler
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]]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

5

更新于:2021年10月18日

392 次浏览

启动您的职业生涯

完成课程获得认证

开始
广告