โปรแกรมหาที่ดินที่ห่างจากน้ำมากที่สุดใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี 0 = น้ำ, 1 = ที่ดิน ต้องการหาที่ดินที่มีระยะทางแมนฮัตตัน (Manhattan distance) จากน้ำมากที่สุด และคืนระยะทางนั้น

เช่น เมทริกซ์:

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

ขั้นตอนการแก้ปัญหา (Multi-source BFS)

• ถ้า A ว่าง คืน 0
• R, C := แถว, คอลัมน์
• distance := matrix R x C เติม 0
• q := deque ใส่ทุก (r,c) ที่ A[r][c] == 0 (น้ำทั้งหมดเป็น source)
• ถ้า len(q) == 0 หรือ R*C คืน -1 (ไม่มีน้ำหรือไม่มีที่ดิน)
• BFS: ดึง (r,c) จากคิว ตรวจสอบ 4 ทิศทาง:
  • ถ้าอยู่ในขอบเขตและ A[x][y] == 1:
    • A[x][y] = 0 (mark visited)
    • distance[x][y] = distance[r][c] + 1
    • เพิ่ม (x,y) เข้าคิว
• คืน max ของค่าสูงสุดในแต่ละแถวของ distance

ตัวอย่างโค้ด

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

ข้อมูลนำเข้า

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

ผลลัพธ์

3