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

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

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 1 ซึ่งจะเชื่อมต่อ (1,0) ถึง (1,2) จุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• row :=จำนวนแถวของเมทริกซ์

• col :=จำนวนคอลัมน์ของเมทริกซ์

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา i, j, s

• ถ้า (i, j) อยู่ใน s แล้ว

  • กลับ

• ถ้า mat[i, j] เท่ากับ 0 แล้ว

  • กลับ

• ใส่ (i, j) ลงใน s

• ถ้า i - 1>=0 แล้ว

  • dfs(i - 1, j, s)

• ถ้าฉัน + 1 <แถว แล้ว

  • dfs(i + 1, j, s)

• ถ้า j - 1>=0 แล้ว

  • dfs(i, j - 1, s)

• ถ้า j + 1

  • dfs(i, j + 1, s)

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• เห็นแล้ว :=ชุดใหม่

• สำหรับผมอยู่ในช่วง 0 ถึงแถว ทำ

  • ถ้าขนาดเห็น> 0 แล้ว

    • ออกจากวง

  • สำหรับ j ในช่วง 0 ถึง col ทำ

    • ถ้า mat[i, j] เหมือนกับ 1 แล้ว

      • dfs(i, j, เห็น)

      • ออกจากวง

• q :=คิวที่สิ้นสุดสองครั้ง

• สำหรับแต่ละดินแดนที่มองเห็นให้ทำ

  • (i, j) :=ที่ดิน

  • ถ้า i - 1>=0 และ mat[i - 1, j] เท่ากับ 0 แล้ว

    • แทรก (i - 1, j, 1) ต่อท้าย q

  • ถ้า i + 1

    • แทรก (i + 1, j, 1) ที่ส่วนท้ายของ q

  • ถ้า j - 1>=0 และ mat[i, j - 1] เท่ากับ 0 แล้ว

    • แทรก (i, j - 1, 1) ต่อท้าย q

  • ถ้า j + 1

    • แทรก (i, j + 1, 1) ที่ส่วนท้ายของ q

• ในขณะที่ขนาดของ q> 0 ทำ

  • (i, j, dist) :=รายการที่เหลือของ q และลบรายการออกจากด้านซ้ายของ q

  • ถ้าเห็น (i, j) แล้ว

    • ไปทำซ้ำต่อไป

  • ทำเครื่องหมาย (i, j) ตามที่เห็น

  • ถ้า mat[i, j] เหมือนกับ 1 แล้ว

    • กลับ dist - 1

  • ถ้า i - 1>=0 แล้ว

    • แทรก (i - 1, j, dist + 1) ที่ส่วนท้ายของ q

  • ถ้า i + 1 <แถวไม่เป็นศูนย์ ดังนั้น

    • แทรก (i + 1, j, dist + 1) ที่ส่วนท้ายของ q

  • ถ้า j - 1>=0 แล้ว

    • แทรก (i, j - 1, dist + 1) ที่ส่วนท้ายของ q

  • ถ้า j + 1

    • แทรก (i, j + 1, dist + 1) ที่ส่วนท้ายของ q

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

import collections
class Solution:
   def solve(self, mat):
      row = len(mat)
      col = len(mat[0])
      def dfs(i, j, s):
         if (i, j) in s:
            return
         if mat[i][j] == 0:
            return
         s.add((i, j))
         if i - 1 >= 0:
            dfs(i - 1, j, s)
         if i + 1 < row:
            dfs(i + 1, j, s)
         if j - 1 >= 0:
            dfs(i, j - 1, s)
         if j + 1 < col:
            dfs(i, j + 1, s)
      seen = set()
      for i in range(row):
         if len(seen) > 0:
            break
         for j in range(col):
            if mat[i][j] == 1:
               dfs(i, j, seen)
               break
      q = collections.deque()
      for land in seen:
         i, j = land
         if i - 1 >= 0 and mat[i - 1][j] == 0:
            q.append((i - 1, j, 1))
         if i + 1 < row and mat[i + 1][j] == 0:
            q.append((i + 1, j, 1))
         if j - 1 >= 0 and mat[i][j - 1] == 0:
            q.append((i, j - 1, 1))
         if j + 1 < col and mat[i][j + 1] == 0:
            q.append((i, j + 1, 1))
      while len(q) > 0:
         i, j, dist = q.popleft()
         if (i, j) in seen:
            continue
         seen.add((i, j))
         if mat[i][j] == 1:
            return dist - 1
         if i - 1 >= 0:
            q.append((i - 1, j, dist + 1))
         if i + 1 < row:
            q.append((i + 1, j, dist + 1))
         if j - 1 >= 0:
            q.append((i, j - 1, dist + 1))
         if j + 1 < col:
            q.append((i, j + 1, dist + 1))
ob = Solution()
matrix = [
   [0, 0, 1],
   [1, 0, 1],
   [1, 0, 0],
]
print(ob.solve(matrix))

อินพุต

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

ผลลัพธ์

1