मान लीजिए हमारे पास एक ग्रिड है, जिसमें 1 मिलियन पंक्तियाँ और 1 मिलियन कॉलम हैं, हमारे पास अवरुद्ध कोशिकाओं की एक सूची भी है। अब हम स्रोत वर्ग से शुरू करेंगे और लक्ष्य वर्ग तक पहुंचना चाहेंगे। प्रत्येक चाल में, हम ग्रिड में ऊपर, नीचे, बाएं, दाएं आसन्न वर्ग पर चल सकते हैं जो अवरुद्ध कोशिकाओं की दी गई सूची में नहीं है।
हमें जांचना है कि क्या चालों के अनुक्रम के माध्यम से लक्ष्य वर्ग तक पहुंचना संभव है या नहीं।
इसलिए, यदि इनपुट इस तरह है 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 का आकार > 20000 या (x,y) target है, तो
true लौटाएं
dfs(x+1,y,target,seen) या dfs(x-1,y,target,seen) या dfs(x,y+1,target,seen) या dfs(x,y-1,target,seen) लौटाएं
dfs(source[0], source[1], target, खाली सेट) और dfs(target[0], target[1], source, खाली सेट) लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
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
