একটি সর্টেড লিস্ট stones দেওয়া আছে যা নদীর স্টোন পজিশন নির্দেশ করে। শেষ স্টোন-এ পৌঁছাতে হবে। প্রতিটি জাম্পে গত জাম্পের দূরত্ব k হলে পরবর্তী জাম্প k-1, k, k+1 হতে পারে। নদী পার করা সম্ভব কিনা বের করতে হবে।
উদাহরণস্বরূপ, stones = [0,1,3,4,5,6,8,9,13] হলে আউটপুট True। পথ: ০→১ (১), ১→৩ (২), ৩→৫ (২), ৫→৮ (৩), ৮→১৩ (৫)।
সমাধানের পদ্ধতি (DFS + মেমোরাইজেশন / ব্যাকট্র্যাকিং)
start = stones[0], end = stones[-1]।stonesকে সেট-এ কনভার্ট করুন O(1) লুকআপের জন্য।check(pos, prev)রিকার্সিভ ফাংশন:- যদি
pos == end:True। jump=prev-1, prev, prev+1এর জন্য:- যদি
jump >= 1এবংpos+jump in stonesএবংcheck(pos+jump, jump)→True।
- যদি
Falseরিটার্ন।
- যদি
check(start, 0)কল করুন।
পাইথন কোড উদাহরণ
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
