โปรแกรมหาความห่างของสะพานสั้นที่สุดระหว่างเกาะใน Python

ได้รับเมทริกซ์ไบนารีที่ 0 แทนน้ำ และ 1 แทนบก เกาะคือกลุ่มของ 1 ที่ติดกันใน 4 ทิศทาง (บน ล่าง ซ้าย ขวา) เราต้องการหาความยาวของสะพานสั้นที่สุดที่เชื่อมต่อสองเกาะเข้าด้วยกัน

ตัวอย่าง

0 0 1
1 0 1
1 0 0

ผลลัพธ์คือ 1 เพราะสามารถเชื่อมจุด (1,0) กับ (1,2) ได้โดยสร้างสะพานยาว 1 หน่วย

แนวทางแก้ปัญหา

1. DFS เพื่อหาเกาะแรกและเก็บพิกัดทั้งหมดไว้ในเซต seen
2. Multi-source BFS เริ่มจากเซลล์น้ำที่ติดกับเกาะแรก (ระยะทาง = 1)
3. ขยาย BFS จนกว่าจะพบเซลล์บกของเกาะที่สอง
4. คืนค่า distance - 1 เมื่อพบเกาะที่สอง

การใช้งาน (Python)

import collections

class Solution:
    def solve(self, mat):
        row, col = len(mat), len(mat[0])
        
        def dfs(i, j, s):
            if (i, j) in s or mat[i][j] == 0:
                return
            s.add((i, j))
            for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < row and 0 <= nj < col:
                    dfs(ni, nj, s)
        
        # หาเกาะแรก
        seen = set()
        for i in range(row):
            for j in range(col):
                if mat[i][j] == 1:
                    dfs(i, j, seen)
                    break
            if seen:
                break
        
        # BFS จากขอบเกาะแรก
        q = collections.deque()
        for i, j in seen:
            for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < row and 0 <= nj < col and mat[ni][nj] == 0:
                    q.append((ni, nj, 1))
        
        while q:
            i, j, dist = q.popleft()
            if (i, j) in seen:
                continue
            seen.add((i, j))
            if mat[i][j] == 1:
                return dist - 1
            for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < row and 0 <= nj < col:
                    q.append((ni, nj, dist + 1))

# ทดสอบ
ob = Solution()
matrix = [[0,0,1], [1,0,1], [1,0,0]]
print(ob.solve(matrix))  # Output: 1

ความซับซ้อน

• Time Complexity: O(row × col)
• Space Complexity: O(row × col)