Chương trình tìm vị trí cuối cùng của các động vật di chuyển khi dừng lại trong Python

Cho chuỗi s mô tả trạng thái ban đầu: 'L' (sang trái), 'R' (sang phải), '@' (đứng yên). Động vật di chuyển sẽ "đẩy" động vật khác trừ khi gặp lực ngược chiều → đứng yên ('@'). Tìm trạng thái cuối cùng.

Ví dụ: "@@L@R@@@@L" → "LLL@RRRLLL".

Giải thuật (BFS đa nguồn theo level)

1. Khởi tạo mảng levels = -1, hàng đợi q chứa các vị trí ban đầu có 'L'/'R' với level 0.
2. BFS: lấy (idx, level, dir) từ queue.
   • Nếu levels[idx] == -1: gán level, cập nhật l[idx] = dir, đẩy láng giềng theo hướng dir với level+1.
   • Nếu levels[idx] == level và l[idx] != dir: va chạm → l[idx] = '@'.

Ví dụ minh họa

from collections import deque

class Solution:
    def solve(self, s):
        levels = [-1] * len(s)
        q = deque()
        for idx, ch in enumerate(s):
            if ch in 'RL':
                q.append((idx, 0, ch))
        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))  # Output: LLL@RRRLLL

Đầu vào / Đầu ra

Input: "@@L@R@@@@L"

Output: "LLL@RRRLLL"