Pythonを使用してすべての部分行列をカウントするプログラム

m x nのバイナリ行列があるとすると、すべての部分行列がいくつあるかを調べる必要があります。

したがって、入力が次のような場合

6（1x1）行列、3（2,1）行列、2（1x2）行列、1（3x1）行列、1（4x4）行列があるため、出力は13になります。

これを解決するには、次の手順に従います-

• m：=行列の行数

• n：=行列の列数

• dp：=同じサイズのゼロ行列m x n

• 0からm-1の範囲のiの場合、実行

  • 0からn-1の範囲のjの場合、実行

    • iが0およびmatrix[i、j]と同じである場合、

      • dp [i、j]：=1

    • それ以外の場合、matrix [i] [j]がゼロ以外の場合、

      • dp [i、j]：=dp [i-1、j] + 1

• 合計：=0

• 0からm-1の範囲のiの場合、実行

  • 0からn-1の範囲のjの場合、実行

    • j + 1からnの範囲のkについては、次のようにします

      • 合計：=合計+最小のdp [i、j]からdp [i、k]

• 合計を返す

理解を深めるために、次の実装を見てみましょう-

例

def solve(matrix):
   m = len(matrix)
   n = len(matrix[0])
   dp = [[0] * n for _ in range(m)]
   for i in range(m):
      for j in range(n):
         if i == 0 and matrix[i][j]:
            dp[i][j] = 1
         elif matrix[i][j]:
            dp[i][j] = dp[i-1][j] + 1
   total = 0
   for i in range(m):
      for j in range(n):
         for k in range(j+1, n+1):
            total += min(dp[i][j:k])
   return total
matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))

入力

[4,6,7,8], 11

出力

13