একটি বড় গোলকধাঁধা পাইথন এস্কেপ

ধরুন আমাদের একটি গ্রিড আছে, সেখানে 1 মিলিয়ন সারি এবং 1 মিলিয়ন কলাম রয়েছে, আমাদের কাছে ব্লক করা ঘরগুলির একটি তালিকাও রয়েছে। এখন আমরা উৎস বর্গ থেকে শুরু করব এবং লক্ষ্য স্কোয়ারে পৌঁছতে চাই। প্রতিটি পদক্ষেপে, আমরা গ্রিডের একটি উপরে, নিচে, বাম, ডান পাশের বর্গক্ষেত্রে যেতে পারি যা ব্লক করা কক্ষের প্রদত্ত তালিকায় নেই।

চালের ক্রমানুসারে লক্ষ্য স্কোয়ারে পৌঁছানো সম্ভব কি না তা আমাদের পরীক্ষা করতে হবে।

সুতরাং, যদি ইনপুটটি ব্লক করা হয় =[[0,1], [1,0]], উৎস =[0,0], লক্ষ্য =[0,3], তাহলে আউটপুটটি মিথ্যা হবে

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ব্লকড :=সমস্ত ব্লক করা সেলের একটি সেট তৈরি করুন

• একটি পদ্ধতি সংজ্ঞায়িত করুন 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,টার্গেট, দেখা)

• 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