Pythonを使用してすべてのもので正方形の部分行列の数を数えるプログラム

m x nのバイナリ行列があるとすると、すべてが1である正方形の部分行列の数を見つける必要があります。

したがって、入力が次のようになっている場合。

辺1が10個、辺2が4個、辺3が1個あるため、出力は15になります。次に、正方形の総数=10 + 4 + 1=15です。

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

• 行列に単一の行列がある場合、

  • 1を返す

• 行：=行列の行数

• cols：=行列の列数[0]

• 結果：=0

• 0から行-1までの範囲の行の場合、実行

  • 0からcols-1の範囲のcolの場合、実行します

    • 行が0と同じか、列が0と同じ場合、

      • matrix [row、col]が1と同じ場合、

        • 結果：=結果+ 1

      • それ以外の場合、matrix [row、col]が1と同じ場合、

        • square：=1 +（matrix [row-1、col]、matrix [row、col-1]およびmatrix [row-1、col-1]の最小値）

        • matrix [row、col]：=square

        • 結果：=結果+正方形

• 結果を返す

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

例

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