Pythonの特定の行列で1の最大の正方形の領域を見つけるプログラム

バイナリ行列があるとすると、その与えられた行列で1の最大の2乗を見つける必要があります。

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

その場合、出力は16になります。

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

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

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

例

class Solution:
   def solve(self, matrix):
      res = 0
      for i in range(len(matrix)):
         res = max(res, matrix[i][0])
      for i in range(len(matrix[0])):
         res = max(res, matrix[0][i])

      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i][j - 1]) + 1

               res = max(res, matrix[i][j])

      return res * res

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

入力

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

出力

16