পাইথনে বড় মেজ থেকে পলায়ন

ধরুন একটি গ্রিড আছে যার ১ মিলিয়ন সারি এবং ১ মিলিয়ন কলাম রয়েছে, আরো একটি ব্লক করা সেলের তালিকা রয়েছে। আমরা سورস স্কোয়ার থেকে শুরু করে টার্গেট স্কোয়ারে পৌঁছাতে চাই। প্রতিটি মুভে আমরা গ্রিডের আপ, ডাউন, লেফট, রাইট সन्नিহিত স্কোয়ারে যেতে পারি যা ব্লক করা তালিকায় নেই।

আমাদের যাচাই করতে হবে কোন সিকোয়েন্সের মাধ্যমে টার্গেট স্কোয়ারে পৌঁছানো সম্ভব কিনা।

যেমন ইনপুট blocked = [[0,1],[1,0]], source = [0,0], target = [0,3] হলে আউটপুট হবে False।

সমাধানের ধাপগুলো −

blocked := সমস্ত ব্লক করা সেলের একটি সেট তৈরি করুন
একটি dfs() মেথড সংজ্ঞায়িত করুন যা x, y, target এবং seen নেবে
যদি (x,y) গ্রিডের রেঞ্জের বাইরে থাকে অথবা (x,y) blocked-এ থাকে অথবা (x,y) seen-এ থাকে তবে false রিটার্ন করুন
(x,y) কে seen-এ যোগ করুন
যদি seen-এর আকার ২০০০০-এর চেয়ে বড় হয় অথবা (x,y) target হয় তবে true রিটার্ন করুন
চার দিকের রিকার্সিভ কলের ফলাফল OR করে রিটার্ন করুন
শেষে source থেকে target এবং target থেকে source দুটো DFS কল করে AND করুন

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য −

উদাহরণ

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