पायथन में चेक करें कि क्या पत्थरों से नदी पार की जा सकती है

मान लीजिए हमारे पास stones नामक सॉर्टेड संख्याओं की एक लिस्ट है जो नदी पर पत्थरों की स्थिति दर्शाती है जिसे हम पार करने की कोशिश कर रहे हैं। नदी पार करने के लिए, हमें अंतिम पत्थर पर समाप्त होना होगा। अब प्रत्येक चरण में, हम (k - 1, k, या k + 1) कदम आगे कूद सकते हैं जहां k अंतिम कूद की दूरी है। हमें चेक करना है कि क्या हम नदी पार कर सकते हैं या नहीं।

उदाहरण के लिए, यदि इनपुट stones = [0, 1, 3, 4, 5, 6, 8, 9, 13] है, तो आउटपुट True होगा, क्योंकि हम 0 से शुरू कर सकते हैं, फिर 1 यूनिट कूदकर पत्थर 1 पर जाएं, फिर 2 यूनिट कूदकर 3 पर, फिर 2 यूनिट कूदकर 5 पर, फिर 3 यूनिट कूदकर 8 पर, और अंत में 5 यूनिट कूदकर 13 पर जाएं, जो अंतिम स्थान है।

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम रिकर्सन + मेमोइजेशन (DFS) का उपयोग करेंगे:

• start := A[0], end := A का अंतिम तत्व
• A := A के सभी यूनिक तत्वों का सेट
• check(pos=start, prev=0) फंक्शन परिभाषित करें:
  • यदि pos == end है, तो True लौटाएं
  • प्रत्येक jump के लिए [prev-1, prev, prev+1] में:
    • यदि jump >= 1 है:
      • next_pos := jump + pos
      • यदि next_pos, A में है और check(next_pos, jump) True है, तो True लौटाएं
  • False लौटाएं
• मुख्य मेथड से check() कॉल करें और परिणाम लौटाएं

पायथन कार्यान्वयन

class Solution:
    def solve(self, A):
        start, end = A[0], A[-1]
        A = set(A)
        def check(pos=start, prev=0):
            if pos == end:
                return True
            for jump in [prev - 1, prev, prev + 1]:
                if jump >= 1:
                    next_pos = jump + pos
                    if next_pos in A and check(next_pos, jump):
                        return True
            return False
        return check()

ob = Solution()
stones = [0, 1, 3, 4, 5, 6, 8, 9, 13]
print(ob.solve(stones))

इनपुट

[0, 1, 3, 4, 5, 6, 8, 9, 13]

आउटपुट

True