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

สมมติว่าเรามีเมทริกซ์ไบนารีโดยที่ 0 แทนน้ำและ 1 แทนดิน ตอนนี้เราต้องหาที่ดินที่มีระยะทางห่างจากน้ำในแมนฮัตตันมากที่สุดและสุดท้ายก็กลับระยะทาง

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

จากนั้นเอาต์พุตจะเป็น 3 เนื่องจากเซลล์ [0,0] เซลล์มีระยะห่างแมนฮัตตัน 3 จากน้ำ

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

• ถ้า A ว่างเปล่า แล้ว
  • คืน 0
• R :=จำนวนแถวของเมทริกซ์, C :=จำนวนคอลัมน์ของเมทริกซ์
• ระยะทาง :=เมทริกซ์ของคำสั่ง R x C และเติมด้วย 0
• q :=คิวคู่ที่มีบางคู่ (r, c) โดยที่ r และ c เป็นดัชนีแถวและคอลัมน์ของเมทริกซ์โดยที่ matrix[r, c] คือ 0
• ถ้าขนาดของ q เหี่ยวเฉา 0 หรือ R * C แล้ว
  • คืน -1
• ในขณะที่ q ไม่ว่างเปล่า ให้ทำ
  • (r, c) :=องค์ประกอบด้านซ้ายของ q จากนั้นลบออกจาก q
  • สำหรับแต่ละคู่ (x, y) ใน [(r - 1, c) ,(r + 1, c) ,(r, c + 1) ,(r, c - 1) ] ทำ
    • ถ้า x และ y อยู่ในช่วงของเมทริกซ์และ A[x, y] คือ 1 แล้ว
      • A[x, y] :=0
      • ระยะทาง[x, y] :=ระยะทาง[r, c] + 1
      • แทรก (x, y) ที่ส่วนท้ายของ q
• res :=รายการที่มีองค์ประกอบสูงสุดของแต่ละแถว
• คืนความละเอียดสูงสุด

ตัวอย่าง (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))

อินพุต

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

ผลลัพธ์

3