मान लीजिए हमारे पास एक ग्रिड है, 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,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