Python में घर पहुंचने के लिए न्यूनतम जंप खोजने का प्रोग्राम

मान लीजिए एक ऐरे forbidden है, जहां forbidden[i] दर्शाता है कि बग forbidden[i] पोजीशन पर जंप नहीं कर सकता, और हमारे पास तीन मान a, b, और x भी हैं। एक बग का घर संख्या रेखा पर पोजीशन x पर है। यह शुरू में पोजीशन 0 पर है। यह निम्नलिखित नियमों से जंप कर सकता है:

बग ठीक a पोजीशन दाएं जंप कर सकता है।
बग ठीक b पोजीशन बाएं जंप कर सकता है।
बग लगातार दो बार पीछे की ओर जंप नहीं कर सकता।
बग ऐरे में दिए गए किसी भी फॉरबिडन पोजीशन पर जंप नहीं कर सकता।
बग अपने घर से आगे जंप कर सकता है, लेकिन यह नेगेटिव मान वाली पोजीशन पर जंप नहीं कर सकता।

हमें बग के गंतव्य तक पहुंचने के लिए आवश्यक न्यूनतम जंप की संख्या ढूंढनी है। यदि ऐसा कोई संभावित अनुक्रम नहीं है, तो -1 वापस करें।

उदाहरण के लिए, यदि इनपुट है forbidden = [2,3,7,9,12], a = 4, b = 2, x = 16, तो आउटपुट 7 होगा क्योंकि, 0 से शुरू करके, a = 4 आगे दो बार जंप करके 4 और 8 पर पहुंचें, लेकिन 12 पर जंप नहीं कर सकते क्योंकि यह फॉरबिडन है, फिर b = 2 पीछे 6 पर जाएं, फिर 10, 14, 18 पर जंप करें और फिर दो बार पीछे जाकर 16 पर पहुंचें, तो कुल 7 चरण हैं।

समाधान के चरण

queue := [(x, 0, True)] के साथ एक क्यू, forbidden := set(forbidden)
lim := max(max(forbidden), x) + a + b
while queue:
- (curr, jumps, is_b) := queue.pop(0)
- यदि curr in forbidden या not (0 <= curr <= lim):
  - अगले इटरेशन पर जाएं
- forbidden.add(curr)
- यदि curr == 0:
  - jumps वापस करें
- यदि is_b:
  - queue.append((curr+b, jumps+1, False))
- queue.append((curr-a, jumps+1, True))
-1 वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(forbidden, a, b, x):
    queue, forbidden = [(x, 0, True)], set(forbidden)
    lim = max(max(forbidden), x) + a + b
    while queue:
        curr, jumps, is_b = queue.pop(0)
        if curr in forbidden or not 0 <= curr <= lim:
            continue
        forbidden.add(curr)
        if curr == 0:
            return jumps
        if is_b:
            queue.append((curr+b, jumps+1, False))
        queue.append((curr-a, jumps+1, True))
    return -1

forbidden = [2,3,7,9,12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x))

इनपुट

[2,3,7,9,12], 4, 2, 16