পাইথনে লাস্ট ইনডেক্সে পৌঁছানোর ন্যূনতম স্টেপ বের করার প্রোগ্রাম (জাম্প গেম ভেরিয়েন্ট)

• pos := defaultdict(list) (ইনডেক্স স্টোর করার ম্যাপ)
• প্রতিটি ইনডেক্স i এবং ভ্যালু n এর জন্য nums-এ:
  • i কে pos[n]-র শেষে ঢুকান।
• n := len(nums)
• visited := [False] * n, visited[0] := True
• q := deque([(0, 0)]) (BFS কিউ)
• q খালি না হওয়া পর্যন্ত লুপ চালান:
  • (u, d) := q.popleft()
  • যদি u == n-1 হয়, তবে d রিটার্ন করুন।
  • pos[nums[u]] + [u-1, u+1] এর প্রতিটি v এর জন্য:
    • যদি 0 <= v < n এবং not visited[v] হয়, তবে:
      • visited[v] := True
      • q.append((v, d+1))
  • del pos[nums[u]] (ভিজিটেড ভ্যালুর ইনডেক্স লিস্ট ডিলিট করে রিডান্ডেন্সি কমাতে)

class Solution:
    def solve(self, nums):
        from collections import defaultdict, deque
        pos = defaultdict(list)
        for i, n in enumerate(nums):
            pos[n].append(i)
        q = deque([(0, 0)])
        n = len(nums)
        visited = [False] * n
        visited[0] = True
        while q:
            u, d = q.popleft()
            if u == n - 1:
                return d
            for v in pos[nums[u]] + [u - 1, u + 1]:
                if 0 <= v < n and not visited[v]:
                    visited[v] = True
                    q.append((v, d + 1))
            del pos[nums[u]]
        return -1

ob = Solution()
nums = [4, 8, 8, 5, 4, 6, 5]
print(ob.solve(nums))

[4, 8, 8, 5, 4, 6, 5]

3