Chương trình tìm giá trị k tối đa để duy trì khoảng cách an toàn trong Python

Cho ma trận nhị phân: 0 (trống), 1 (người). Khoảng cách giữa hai ô = max(|dx|, |dy|) (Chebyshev distance). Ma trận an toàn với yếu tố k nếu tồn tại ô trống mà khoảng cách từ ô đó đến mọi người và đến mọi cạnh ma trận đều ≥ k. Tìm k lớn nhất.

Ví dụ ma trận 5x5 cho kết quả 1.

Giải pháp

Biến đổi bài toán thành tìm hình vuông lớn nhất toàn 0 trong ma trận đảo ngược:

• Đảo bit ma trận: 0↔1 (người thành 0, trống thành 1)
• DP tìm hình vuông toàn 1 lớn nhất: A[i][j] = 1 + min(A[i-1][j], A[i][j-1], A[i-1][j-1]) nếu A[i][j]==1
• ans = max side length của hình vuông toàn 1
• Kết quả = (ans + 1) // 2

Ví dụ minh họa

class Solution:
    def solve(self, A):
        N = len(A)
        M = len(A[0])
        for i in range(N):
            for j in range(M):
                A[i][j] ^= 1
        ans = 0
        for i in range(N):
            for j in range(M):
                if i and j and A[i][j]:
                    A[i][j] = 1 + min(A[i-1][j], A[i][j-1], A[i-1][j-1])
                    ans = max(A[i][j], ans)
        return (ans + 1) // 2

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

Đầu vào

[[0,0,0,0,0],[0,1,1,1,0],[0,1,0,1,0],[0,1,1,1,0],[0,0,0,0,0]]

Đầu ra

1