หลบหนีจากเขาวงกตเขาวงกตขนาดใหญ่

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

เราต้องตรวจสอบก่อนว่าจะไปถึงช่องเป้าหมายโดยลำดับการเคลื่อนที่ได้หรือไม่

ดังนั้น หากอินพุตเหมือนถูกบล็อก =[[0,1],[1,0]], source =[0,0], target =[0,3] ผลลัพธ์จะเป็นเท็จ

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

• blocked :=สร้างชุดของเซลล์ที่ถูกบล็อกทั้งหมด

• กำหนดหนึ่งวิธี dfs() ซึ่งจะใช้เวลา x, y, เป้าหมายและเห็น

• ถ้า (x,y) ไม่อยู่ในช่วงของกริดหรือ (x,y) อยู่ในบล็อคหรือ (x,y) อยู่ในระยะที่มองเห็นได้

  • คืนค่าเท็จ

  • 
    

• เติม (x,y) เข้าไป

• ถ้าขนาดของการมองเห็น> 20000 หรือ (x,y) เป็นเป้าหมายแล้ว

  • คืนความจริง

• ส่งคืน dfs(x+1,y,target,seen) หรือ dfs(x-1,y,target,seen) หรือ dfs(x,y+1,target,seen) หรือ dfs(x,y-1,target, เห็นแล้ว)

• ส่งคืน dfs(แหล่งที่มา[0], แหล่งที่มา[1], เป้าหมาย, ชุดว่าง) และ dfs(เป้าหมาย[0], เป้าหมาย[1], แหล่งที่มา, ชุดว่าง)

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

ตัวอย่าง

class Solution(object):
   def isEscapePossible(self, blocked, source, target):
      blocked = set(map(tuple, blocked))
      def dfs(x, y, target, seen):
         if not (0 <= x < 10**6 and 0 <= y < 10**6) or (x, y) in blocked or (x, y) in seen: return             False
         seen.add((x, y))
         if len(seen) > 20000 or [x, y] == target: return True
         return dfs(x + 1, y, target, seen) or \
            dfs(x - 1, y, target, seen) or \
            dfs(x, y + 1, target, seen) or \
            dfs(x, y - 1, target, seen)
         return dfs(source[0], source[1], target, set()) and
dfs(target[0], target[1], source, set())
ob = Solution()
print(ob.isEscapePossible([[0,1],[1,0]], [0,0], [0,3]))

อินพุต

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

ผลลัพธ์

False