用 Python 编写程序来计算给定二进制矩阵中方阵子矩阵的数量

假设我们有一个 2D 二进制矩阵。我们必须找到矩阵中所有元素均为 1 的方格子矩阵的总数。

因此，如果输入如下

则输出将为 5，因为有一个(2 × 2)方格和四个(1 × 1)方格

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

• 如果 mat 为空，则
  • 返回 0
• c := 0
• for i in range 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

  示例

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

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

  输出

  5
  

  ---

  相关文章

  • Python - 使用交替的 0 和 1 初始化列表
  • Python 中元组列表到字典的转换
  • Python - 从两个列表中配对，使得成对的元素不相同
  • 使用 Python 和 SQLite 的 SQL
  • 使用 pytrie 模块在 Python 中进行前缀匹配
  • 创建和访问 Python 包
  • 如何使用正则表达式和数据类型选择多个 DataFrame 列
  • 如何在 Pandas 中查找和过滤重复行?
  • 用 Python 编写程序以正确的顺序查找机场?
  • 如何在 Python Pandas 中使用字典顺序切片选择数据子集?

  ---

  有用资源

  • python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

  ---

  打印 下一节:用 Python 编写程序来计算二进制字符串中全为 1 的子字符串数量 ❯❮ 上一节:用 Python 编写程序来计算完全包含在其他间隔内的间隔数