Chương trình tìm ô đất xa nước nhất (theo khoảng cách Manhattan) trong Python

Cho ma trận nhị phân (0: nước, 1: đất). Tìm ô đất có khoảng cách Manhattan lớn nhất đến nước gần nhất, trả về khoảng cách đó.

Ví dụ ma trận 4x4:

1 1 1 1
1 1 0 1
1 1 1 1
0 0 1 1

Giải thuật (BFS đa nguồn - Multi-source BFS)

• Khởi tạo hàng đợi q chứa tất cả ô nước (giá trị 0).
• Nếu không có nước hoặc toàn bộ là nước → trả về -1.
• BFS: lấy ô khỏi hàng đợi, lan truyền đến 4 ô kề là đất (1):
  • Đánh dấu ô đất thành nước (0) để không thăm lại.
  • Gán khoảng cách = khoảng cách ô hiện tại + 1.
  • Đẩy vào hàng đợi.
• Kết quả là giá trị lớn nhất trong ma trận khoảng cách.

Mã nguồn Python

from collections import deque

class Solution:
    def solve(self, A):
        if not A:
            return 0
        R, C = len(A), len(A[0])
        distance = [[0]*C for _ in range(R)]
        q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c])
        if len(q) in (0, R * C):
            return -1
        while q:
            r, c = q.popleft()
            for x, y in [(r-1,c), (r+1,c), (r,c+1), (r,c-1)]:
                if 0 <= x < R and 0 <= y < C and A[x][y]:
                    A[x][y] = 0
                    distance[x][y] = distance[r][c] + 1
                    q.append((x, y))
        return max(max(row) for row in distance)

ob = Solution()
matrix = [[1,1,1,1],[1,1,0,1],[1,1,1,1],[0,0,1,1]]
print(ob.solve(matrix))  # Output: 3

Đầu vào

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

Đầu ra

3