पायथन में घर पहुंचने के लिए न्यूनतम छलांग लगाने का कार्यक्रम

मान लीजिए कि निषिद्ध नामक एक सरणी है, जहां निषिद्ध [i] इंगित करता है कि बग निषिद्ध स्थिति पर नहीं जा सकता है [i], और हमारे पास तीन मान ए, बी और एक्स भी हैं। एक बग का घर संख्या रेखा पर स्थिति x पर है। यह शुरुआत में 0 की स्थिति में है। यह नियमों का पालन करके कूद सकता है -

बग बिल्कुल सही स्थिति में कूद सकता है।
बग ठीक b स्थिति में बाईं ओर कूद सकता है।
बग लगातार दो बार पीछे नहीं जा सकता।
बग सरणी में दी गई किसी भी निषिद्ध स्थिति पर नहीं जा सकता।
बग अपने घर से आगे कूद सकता है, लेकिन यह नकारात्मक मानों वाले क्रमांकित पदों पर नहीं जा सकता।

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

इसलिए, यदि इनपुट निषिद्ध है =[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 कदम हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

कतार:=एक टपल (x,0,True) के साथ एक कतार, निषिद्ध:=एक नया सेट और निषिद्ध सूची से तत्व सम्मिलित करें
lim :=a + b + (अधिकतम x और निषिद्ध सेट का अधिकतम मान)
जबकि कतार खाली नहीं है, करें
- (curr,jumps,is_b) :=कतार से पहला तत्व और इसे कतार से हटा दें
- अगर curr निषिद्ध है या (0 <=curr <=lim) गलत है, तो
  - अगले पुनरावृत्ति के लिए जाएं
- वर्जित में कर्व डालें
- अगर curr 0 के समान है, तो
  - वापसी कूदता है
- अगर is_b सच है, तो
  - कतार में डालें (curr+b,जंप+1,गलत)
- कतार में डालें (कर-ए,जंप+1,ट्रू)
वापसी -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