หาจำนวนขั้นตอนขั้นต่ำให้ทุกคนพบกันที่เซลล์เดียวกันใน Grid (Python)

บทนำ

ในบทช่วยสอนนี้ เราจะหา จำนวนขั้นตอนขั้นต่ำ ให้ทุกคน (คน = ค่า 2 ใน grid) เดินพบกันที่เซลล์เดียวกัน โดยคนเดินได้ 4 ทิศทาง (บน/ล่าง/ซ้าย/ขวา) หรืออยู่กับที่ ใช้เวลา 1 หน่วยต่อขั้นตอน ผนัง = 1, ทางเดิน = 0

ตัวอย่าง

Grid:

Output: 2 (พบกันที่ [1,1] ทุกคนถึงได้ภายใน 2 ขั้นตอน)

อัลกอริทึม: Multi-source BFS + Intersection

1. รัน BFS จาก ทุกคน (ค่า 2) แยกกัน หาระยะทางไปทุกเซลล์
2. หา Intersection (เซลล์ที่ทุกคนถึงได้) โดยเก็บระยะทางสูงสุด (max) ของแต่ละเซลล์จากทุกคน
3. คำตอบ = min ของ max-distances ทุกเซลล์ใน intersection

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

class Solution:
    def solve(self, A):
        R, C = len(A), len(A[0])
        
        def get_neighbor(r, c):
            for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
                if 0 <= nr < R and 0 <= nc < C and A[nr][nc] & 1 == 0:
                    yield nr, nc
        
        def bfs(r, c):
            queue = [(r, c)]
            dist = {(r, c): 0}
            for r, c in queue:
                if dist[r, c] > 15: break
                for nr, nc in get_neighbor(r, c):
                    if (nr, nc) not in dist:
                        dist[nr, nc] = dist[r, c] + 1
                        queue.append((nr, nc))
            return dist
        
        dist = None
        for r, row in enumerate(A):
            for c, val in enumerate(row):
                if val == 2:
                    ndist = bfs(r, c)
                    if dist is None:
                        dist = ndist
                    else:
                        for key in list(dist.keys()):
                            if key in ndist:
                                dist[key] = max(dist[key], ndist[key])
                            else:
                                del dist[key]
        
        return min(dist.values()) if dist else 0

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

ผลลัพธ์

2

การปรับปรุงประสิทธิภาพ

• ใช้ Multi-source BFS เดียว เริ่มจากทุกคนพร้อมกัน แทนที่จะรัน BFS หลายครั้ง
• ใช้ array แทน dictionary สำหรับ dist
• จำกัดระยะทางสูงสุด (15 ในโค้ด) อาจต้องปรับตามขนาด grid

สรุป

หาจุดพบที่ minimize maximum distance (Minimax) ใช้ BFS จากแต่ละคนหา intersection หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ