โปรแกรมค้นหาจำนวนขั้นตอนขั้นต่ำที่จำเป็นในการพบทุกคนในเซลล์ใด ๆ ใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติซึ่งมีค่าเหล่านี้อยู่:0 หมายถึงเซลล์ว่าง 1 หมายถึง กำแพง 2 หมายถึง บุคคล ตอนนี้บุคคลสามารถเดินสี่ทิศทางขึ้น ลง ซ้าย ขวา มิฉะนั้นให้อยู่ในหน่วยเวลาเดียว เราต้องหาห้องขังที่เดินได้เพื่อลดเวลาที่ทุกคนจะพบเจอและย้อนเวลากลับไป เราต้องจำไว้ว่าคนสองคนสามารถเดินผ่านช่องว่างเปล่าเดียวกันได้ และคุณสามารถสรุปได้ว่าต้องมีเส้นทางระหว่างคนสองคนเสมอ

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

จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากทั้งหมดสามารถพบกันที่เมทริกซ์ตำแหน่ง[1, 1] โดยไม่เกิน 2 ขั้นตอน

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

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

• กำหนดฟังก์ชัน bfs() นี่จะใช้เวลา r, c

• คิว :=กำหนดคิวและแทรกคู่ (r, c) เข้าไป

• dist :=แผนที่ที่มีคู่ค่าคีย์ {(r, c) :0}

• สำหรับแต่ละคู่ (r, c) ในคิว ทำ

  • ถ้า dist[r, c]> 15 ไม่ใช่ศูนย์ ดังนั้น

    • ออกจากวง

  • สำหรับแต่ละเพื่อนบ้าน (nr, nc) ของ (r, c) ทำ

    • ถ้า (nr, nc) ไม่ได้อยู่ใน dist แล้ว

      • dist[nr, nc] :=dist[r, c] + 1

      • แทรก (nr, nc) ที่ท้ายคิว

  • กลับ dist

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

• dist :=null

• สำหรับแต่ละแถวหมายเลข r และองค์ประกอบแถวที่สอดคล้องกันของ A ทำ

  • สำหรับแต่ละคอลัมน์หมายเลข c และค่าของแถว[c] val ทำ

    • ถ้า val เท่ากับ 2 แล้ว

      • ndist :=bfs(r, c)

      • ถ้า dist เป็นโมฆะ

        • dist :=ndist

      • มิฉะนั้น

        • สำหรับแต่ละคีย์ในคีย์ของ dist ให้ทำ

          • ถ้าคีย์อยู่ใน ndist แล้ว

            • dist[key] :=สูงสุดของ dist[key], ndist[key]

          • มิฉะนั้น

            • ลบ dist[คีย์]

• คืนค่าต่ำสุดของค่า dist ทั้งหมดหาก dist ไม่ว่างเปล่ามิฉะนั้นให้คืนค่า 0

ตัวอย่าง

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
ob = Solution()
matrix = [
   [2, 0, 1, 0],
   [1, 0, 0, 2],
   [2, 0, 2, 0]
]
print(ob.solve(matrix))

อินพุต

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

ผลลัพธ์

2