मान लीजिए हम शुरुआती स्थिति p पर हैं, हम किसी भी दिशा (बाएं या दाएं) में d1 और d2 यूनिट कूद सकते हैं। हमें p से कूदकर स्थिति q तक पहुंचने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढनी है।
तो, यदि इनपुट p = 5, q = 10, d1 = 4, d2 = 3 है, तो आउटपुट 3 होगा क्योंकि हम दूरी 4 का उपयोग करके दो बार दाएं कूद सकते हैं फिर हम स्थान 13 पर पहुंच सकते हैं, फिर 3 यूनिट बाएं कूदकर 10 पर पहुंच सकते हैं।
हल करने के चरण
- gcd_res := d1 और d2 का gcd
- यदि (p - q), gcd_res से विभाज्य नहीं है, तो:
- -1 लौटाएं
- que := एक डबल एंडेड क्यू परिभाषित करें
- visited := एक नया सेट
- क्यू में (p, 0) जोड़ी डालें
- p को विज़िटेड के रूप में चिह्नित करें
- जब तक que का आकार > 0 है, तब तक:
- (point, step) := क्यू का फ्रंट एलिमेंट और इसे que से हटाएं
- यदि point, q के समान है, तो:
- step लौटाएं
- यदि point + d1 विज़िटेड नहीं है, तो:
- que में (point + d1, step + 1) जोड़ी डालें
- (point + d1) को विज़िटेड के रूप में चिह्नित करें
- यदि point + d2 विज़िटेड में नहीं है, तो:
- que में (point + d2, step + 1) जोड़ी डालें
- (point + d2) को विज़िटेड के रूप में चिह्नित करें
- यदि point - d1 विज़िटेड में नहीं है, तो:
- que में (point - d1, step + 1) जोड़ी डालें
- (point - d1) को विज़िटेड के रूप में चिह्नित करें
- यदि point - d2 विज़िटेड में नहीं है, तो:
- que में (point - d2, step + 1) जोड़ी डालें
- (point - d2) को विज़िटेड के रूप में चिह्नित करें
उदाहरण
from math import gcd
from collections import deque
def solve(p, d1, d2, q):
gcd_res = gcd(d1, d2)
if (p - q) % gcd_res != 0:
return -1
que = deque()
visited = set()
que.appendleft([p, 0])
visited.add(p)
while len(que) > 0:
pair = que.pop()
point, step = pair[0], pair[1]
if point == q:
return step
if point + d1 not in visited:
que.appendleft([(point + d1), step + 1])
visited.add(point + d1)
if point + d2 not in visited:
que.appendleft([(point + d2), step + 1])
visited.add(point + d2)
if point - d1 not in visited:
que.appendleft([(point - d1), step + 1])
visited.add(point - d1)
if point - d2 not in visited:
que.appendleft([(point - d2), step + 1])
visited.add(point - d2)
p = 5
q = 10
d1 = 4
d2 = 3
print(solve(p, d1, d2, q))
इनपुट
5, 4, 3, 10
आउटपुट
True
