โปรแกรมหาค่า k สูงสุดสำหรับระยะห่างปลอดภัยในเมทริกซ์ไบนารีใน Python

คำอธิบายโจทย์

เมทริกซ์ไบนารี 0=ว่าง 1=คน ระยะห่าง = max(|dx|, |dy|) (Chebyshev distance) เมทริกซ์ปลอดภัย factor k ถ้ามีเซลล์ว่างที่ระยะจากทุกคนและขอบ ≥ k หา k สูงสุด

ตัวอย่าง

เมทริกซ์ 5x5 มีคนกลาง → k = 1 (เซลล์กลางห่างจากคนและขอบ ≥ 1)

วิธีแก้ปัญหา

Largest Empty Square (DP) บนเมทริกซ์ที่ invert แล้ว:

1. Invert เมทริกซ์: 0↔1 (คน→0, ว่าง→1)
2. DP หา largest square ของ 1's: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
3. ans = max dp[i][j]
4. k = (ans + 1) // 2 (เพราะระยะ Chebyshev = radius ของ square)

โค้ด Python

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

อินพุต

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

เอาต์พุต

1