Pythonで1の正方形の部分行列の数を見つけるプログラム

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

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

12（1 x 1）の正方形、4（2 x 2）の正方形、1（3 x 3）の正方形があるため、出力は17になります。

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

• res：=0
• 行列の行数が0から行数の範囲のiについては、
  • 0から行列の列数までの範囲のjの場合、do
    • iが0と同じか、jが0と同じ場合、
      • res：=res + matrix [i、j]
    • それ以外の場合、matrix [i、j]が1と同じ場合、
      • matrix [i、j] =最小値（matrix [i、j-1]、matrix [i-1、j]およびmatrix [i-1、j-1]）+ 1
      • res：=res + matrix [i、j]
• return res

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

例

class Solution:
   def solve(self, matrix):
      res = 0
      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if i == 0 or j == 0:
               res += matrix[i][j]
            elif matrix[i][j] == 1:
               matrix[i][j] = min(matrix[i][j - 1], matrix[i - 1][j], matrix[i - 1][j - 1]) + 1
               res += matrix[i][j]
      return res

ob = Solution()
matrix = [
   [1, 1, 1, 0],
   [1, 1, 1, 0],
   [1, 1, 1, 0],
   [0, 0, 0, 0],
   [1, 0, 1, 1]
]
print(ob.solve(matrix))

入力

matrix = [  
[1, 1, 1, 0],  
[1, 1, 1, 0],  
[1, 1, 1, 0],  
[0, 0, 0, 0],  
[1, 0, 1, 1]
]

出力

17