Pythonで与えられたバイナリ行列の二乗部分行列の数を数えるプログラム

2Dバイナリ行列があるとします。すべての要素が1である、行列に存在する正方形の部分行列の総数を見つける必要があります。

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

1つ（2×2）の正方形と4つの（1×1）の正方形があるため、出力は5になります

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

• マットが空の場合、
  • 0を返す
• c：=0
• 0からマットの行数までの範囲のiについては、
  • 0からマットの列数までの範囲のjについては、
    • 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
• return 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