Chương trình tìm số ma trận con vuông bằng 1 trong python

Giả sử chúng ta có một ma trận nhị phân 2D, chúng ta phải tìm tổng số ma trận con vuông có tất cả 1 s ở đó.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 17 vì có 12 (1 x 1) hình vuông, 4 (2 x 2) hình vuông và 1 (3 x 3) hình vuông.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=0
• đối với tôi trong phạm vi 0 đến số hàng của ma trận, hãy thực hiện
  • đối với j trong phạm vi 0 đến số cột của ma trận, thực hiện
    • nếu tôi giống 0 hoặc j giống 0, thì
      • res:=res + ma trận [i, j]
    • ngược lại khi ma trận [i, j] giống 1, thì
      • ma trận [i, j] =tối thiểu của (ma trận [i, j - 1], ma trận [i - 1, j] và ma trận [i - 1, j - 1]) + 1
      • res:=res + ma trận [i, j]
• trả lại res

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

17