โปรแกรมหาตำแหน่งสุดท้ายของสัตว์เคลื่อนที่เมื่อหยุดใน Python

ได้รับสตริง s แทนสถานะเริ่มต้นของสัตว์: L (ซ้าย), R (ขวา), @ (นิ่ง) สัตว์ที่เคลื่อนที่จะ "ดัน" สัตว์หน้ามันไปด้วย เว้นแต่จะได้แรงจากทิศตรงข้าม → หยุดนิ่ง (@) หาสถานะสุดท้ายเมื่อทุกตัวหยุด

ตัวอย่าง

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

Output: "LLL@RRRLLL"

แนวทางแก้ปัญหา

ใช้ Multi-source BFS (Level-based):

1. คิวเริ่มต้น: ทุกตำแหน่งที่เป็น L หรือ R พร้อม level 0
2. แต่ละขั้น: pop ตำแหน่ง ถ้ายังไม่ถูกกำหนด level → กำหนด level, ตั้งค่าทิศทาง
3. ขยายไปข้างหน้าตามทิศทาง (level+1)
4. ถ้าพบตำแหน่งที่มี level เท่ากันแต่ทิศต่างกัน → ตั้งเป็น @ (ชนกัน)

การใช้งาน (Python)

from collections import deque

class Solution:
    def solve(self, s):
        n = len(s)
        levels = [-1] * n
        q = deque()
        
        # เริ่มจากทุกตัวที่เคลื่อนที่
        for i, ch in enumerate(s):
            if ch in 'LR':
                q.append((i, 0, ch))
        
        result = list(s)
        
        while q:
            idx, level, direction = q.popleft()
            
            if levels[idx] == -1:
                levels[idx] = level
                result[idx] = direction
                # ขยายต่อไป
                if direction == 'R' and idx + 1 < n:
                    q.append((idx + 1, level + 1, direction))
                elif direction == 'L' and idx - 1 >= 0:
                    q.append((idx - 1, level + 1, direction))
            elif levels[idx] == level:
                # ชนกัน: ทิศต่างกัน -> หยุดนิ่ง
                if result[idx] != direction:
                    result[idx] = '@'
        
        return ''.join(result)

# ทดสอบ
ob = Solution()
print(ob.solve("@@L@R@@@@L"))  # Output: LLL@RRRLLL

ความซับซ้อน

• Time Complexity: O(N)
• Space Complexity: O(N)