पायथन में चलते हुए जानवरों की अंतिम स्थिति ज्ञात करने का प्रोग्राम जब वे रुकते हैं

मान लीजिए हमारे पास एक स्ट्रिंग s है जो कुछ जानवरों की प्रारंभिक स्थितियों को दर्शाती है। प्रत्येक जानवर तीन मानों में से एक ले सकता है: L (बाएं चलता है), R (दाएं चलता है), @ (स्थिर खड़ा है)। एक दिशा में चलने वाले जानवर अन्य जानवरों को उठा लेते हैं जब तक कि उन्हें विपरीत दिशा से बल न मिले। तब वे स्थिर खड़े हो जाते हैं। हमें प्रत्येक जानवर की अभिविन्यास ज्ञात करनी है जब वे चलना बंद कर देते हैं।

उदाहरण के लिए, s = "@@L@R@@@@L" के लिए आउटपुट "LLL@RRRLLL" होगा।

एल्गोरिदम (BFS लेवल के साथ)

• levels := s के आकार की सूची -1 से भरी हुई, q := डीक्यू
• प्रत्येक सूचकांक idx के लिए जहां s[idx] 'R' या 'L' है, (idx, 0, s[idx]) को क्यू में डालें
• l := s के वर्णों की सूची
• जब तक क्यू खाली नहीं है:
  • (idx, new_level, dir) := q.popleft()
  • यदि levels[idx] == -1:
    • levels[idx] = new_level, l[idx] = dir
    • यदि dir == "R" और idx+1 < len(l), तो (idx+1, new_level+1, dir) डालें
    • यदि dir == "L" और idx-1 >= 0, तो (idx-1, new_level+1, dir) डालें
  • अन्यथा यदि levels[idx] == new_level और l[idx] != dir, तो l[idx] = "@"
• l को जोड़कर स्ट्रिंग वापस करें

उदाहरण

from collections import deque
class Solution:
    def solve(self, s):
        levels = [-1 for _ in s]
        q = deque()
        for idx in range(len(s)):
            if s[idx] in ("R", "L"):
                q.append((idx, 0, s[idx]))
        l = list(s)
        while q:
            idx, new_level, dir = q.popleft()
            if levels[idx] == -1:
                levels[idx] = new_level
                l[idx] = dir
                if dir == "R" and idx + 1 < len(l):
                    q.append((idx + 1, new_level + 1, dir))
                elif dir == "L" and idx - 1 >= 0:
                    q.append((idx - 1, new_level + 1, dir))
            elif levels[idx] == new_level:
                if l[idx] != dir:
                    l[idx] = "@"
        return "".join(l)

ob = Solution()
s = "@@L@R@@@@L"
print(ob.solve(s))

इनपुट

"@@L@R@@@@L"

आउटपुट

LLL@RRRLLL