Chương trình đếm số lượng ma trận con vuông với tất cả các ma trận con bằng Python

Giả sử chúng ta có m x n ma trận nhị phân, chúng ta phải tìm bao nhiêu ma trận con vuông có tất cả các ma trận đó.

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

thì kết quả đầu ra sẽ là 15, vì có 10 hình vuông của cạnh 1. 4 hình vuông của cạnh 2 và 1 hình vuông của cạnh 3. Khi đó tổng số hình vuông =10 + 4 + 1 =15.

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

• nếu ma trận có một ma trận duy nhất, thì

  • trả lại 1

• row:=số hàng của ma trận

• cols:=số cột của ma trận [0]

• kết quả:=0

• đối với hàng trong phạm vi 0 đến hàng - 1, thực hiện

  • cho col trong phạm vi 0 đến cols - 1, thực hiện

    • nếu hàng giống 0 hoặc col giống 0 thì

      • nếu ma trận [row, col] giống 1, thì

        • kết quả:=kết quả + 1

      • ngược lại khi ma trận [row, col] giống 1 thì

        • vuông:=1 + (tối thiểu của ma trận [row-1, col], ma trận [row, col-1] và ma trận [row-1, col-1])

        • ma trận [row, col]:=square

        • result:=result + square

• trả về kết quả

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

Ví dụ

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

Đầu vào

{{0,1,1,1},{1,1,1,1},{0,1,1,1}}

Đầu ra

15