Chương trình tìm diện tích hình vuông lớn nhất gồm các số 1 trong ma trận cho trước bằng Python

Giả sử chúng ta có một ma trận nhị phân, nhiệm vụ là tìm hình vuông lớn nhất chỉ chứa các số 1 trong ma trận đó.

Ví dụ, nếu đầu vào như sau:

Kết quả đầu ra sẽ là 16.

Giải thuật

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

• Khởi tạo res = 0.
• Duyệt qua cột đầu tiên: cập nhật res bằng giá trị lớn nhất giữa res và matrix[i][0].
• Duyệt qua hàng đầu tiên: cập nhật res bằng giá trị lớn nhất giữa res và matrix[0][i].
• Duyệt từ hàng 1 đến cuối và cột 1 đến cuối:
  • Nếu matrix[i][j] == 1, cập nhật matrix[i][j] = min(matrix[i-1][j], matrix[i-1][j-1], matrix[i][j-1]) + 1.
  • Cập nhật res = max(res, matrix[i][j]).
• Trả về res * res (diện tích hình vuông).

Ví dụ minh họa

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

Đầu vào

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

Đầu ra

16