โปรแกรมตรวจสอบบุคคลสามารถเข้าถึงเซลล์บนซ้ายหรือล่างขวาเพื่อหลีกเลี่ยงไฟหรือไม่ใน Python

สมมติว่าเรามีเมทริกซ์ 2 มิติที่มีค่าต่างกันเล็กน้อยดังนี้ -

• 0 สำหรับเซลล์ว่าง

• 1 สำหรับคน

• 2 สำหรับไฟ

• 3 สำหรับผนัง

ตอนนี้สมมติว่ามีเพียงคนเดียวและในแต่ละเทิร์นไฟจะขยายออกไปทั้งสี่ทิศทาง (ขึ้น ลง ซ้ายและขวา) แต่ไฟไม่สามารถขยายผ่านกำแพงได้ เราต้องตรวจสอบว่าบุคคลนั้นสามารถย้ายไปที่มุมบนซ้ายหรือมุมล่างขวาหรือเมทริกซ์ เราต้องจำไว้ว่าในแต่ละเทิร์น บุคคลจะเคลื่อนที่ก่อน จากนั้นไฟจะขยายตัว หากบุคคลนั้นไปถึงเซลล์เป้าหมายในช่วงเวลาเดียวกับไฟ แสดงว่าเขาปลอดภัย ดังนั้นหากบุคคลไปที่ห้องขังแล้วไฟลุกลามไปยังห้องเดียวกัน บุคคลนั้นก็จะยังรอดอยู่

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

จากนั้นผลลัพธ์จะเป็น True เนื่องจากบุคคลนั้นสามารถไปที่มุมซ้ายบนได้

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

• R :=จำนวนแถวของ A, C :=จำนวนคอลัมน์ของ A

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

• dist :=แผนที่ที่มีคีย์เป็นโหนดของคิวและค่าทั้งหมดเป็น 0

• ขณะที่คิวไม่ว่างให้ทำ

  • node :=รายการซ้ายของคิว จากนั้นลบรายการที่เหลือ

  • สำหรับโหนดเพื่อนบ้านแต่ละโหนดให้ทำ

    • ถ้าเนยไม่อยู่ไกลกัน

      • dist[nei] :=dist[โหนด] + 1

      • ใส่ nei ท้ายคิว

• กลับ dist

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

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

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

• สำหรับแต่ละแถวดัชนี r และแถว A ทำ

  • สำหรับแต่ละคอลัมน์ดัชนี c และค่า v ในแถว ทำ

    • ถ้า v เท่ากับ 1 แล้ว

      • ใส่คู่ (r, c) ที่ส่วนท้ายของ person_que

    • มิฉะนั้นเมื่อ v เท่ากับ 2 แล้ว

      • ใส่คู่ (r, c) ที่จุดสิ้นสุดของ fire_que

      • dist_fire :=bfs(fire_que)

• dist_person :=bfs(person_que)

• สำหรับแต่ละสถานที่ใน (0, 0), (R − 1, C -1) ทำ

  • if (dist_fire[place] ถ้าไม่มีอยู่ INF)>=(dist_person[place] หากไม่มีอยู่ 2 * INF) ดังนั้น

    • คืนค่า True

• คืนค่าเท็จ

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

ตัวอย่าง

from collections import deque
class Solution:
   def solve(self, A):
      INF = int(1e9)
      R, C = len(A), len(A[0])
      def get_nei(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] != 3:
               yield nr, nc
         def bfs(queue):
            dist = {node: 0 for node in queue}
            while queue:
               node = queue.popleft()
               for nei in get_nei(*node):
                  if nei not in dist:
                     dist[nei] = dist[node] + 1
                     queue.append(nei)
            return dist
         fire_que = deque()
         person_que = deque()
         for r, row in enumerate(A):
            for c, v in enumerate(row):
               if v == 1:
                  person_que.append((r, c))
               elif v == 2:
                  fire_que.append((r, c))
         dist_fire = bfs(fire_que)
         dist_person = bfs(person_que)
         for place in ((0, 0), (R− 1, C− 1)):
            if dist_fire.get(place, INF) >= dist_person.get(place, 2 * INF):
               return True
         return False
ob = Solution()
matrix = [
   [0, 0, 0],
   [0, 0, 1],
   [0, 0, 2]
]
print(ob.solve(matrix))

อินพุต

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

ผลลัพธ์

True