Submission #1125425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125425		ALTAKEXE	Robots (APIO13_robots)	Pypy 3	0 / 100	166 ms	43660 KiB

robots

from collections import deque

def parse_input():
    import sys
    input = sys.stdin.read
    data = input().splitlines()
    n, w, h = map(int, data[0].split())
    grid = [list(row) for row in data[1:]]
    robots = {}
    for i in range(h):
        for j in range(w):
            if grid[i][j].isdigit():
                robots[int(grid[i][j])] = (i, j)
    return n, w, h, grid, robots

def rotate(direction, plate):
    # Rotate 90 degrees based on plate type
    if plate == 'A':  # Counter-clockwise
        return (-direction[1], direction[0])
    elif plate == 'C':  # Clockwise
        return (direction[1], -direction[0])
    return direction

def push_robot(grid, robot, direction):
    # Simulate robot movement
    x, y = robot
    dx, dy = direction
    while True:
        nx, ny = x + dx, y + dy
        if nx < 0 or ny < 0 or nx >= len(grid) or ny >= len(grid[0]) or grid[nx][ny] == 'x':
            break
        if grid[nx][ny] in {'A', 'C'}:
            direction = rotate(direction, grid[nx][ny])
            dx, dy = direction
        x, y = nx, ny
    return (x, y)

def bfs(n, w, h, grid, robots):
    initial_state = tuple(sorted(robots.items()))
    queue = deque([(initial_state, 0)])  # (state, push_count)
    visited = set()
    visited.add(initial_state)
    
    while queue:
        state, push_count = queue.popleft()
        # Check if all robots have merged
        if len(state) == 1 and state[0][0] == (1, n):
            return push_count
        
        # Try pushing each robot in all directions
        for i, (label, position) in enumerate(state):
            for direction in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                new_position = push_robot(grid, position, direction)
                new_state = list(state)
                new_state[i] = (label, new_position)
                new_state = tuple(sorted(new_state))
                
                if new_state not in visited:
                    visited.add(new_state)
                    queue.append((new_state, push_count + 1))
    
    return -1

if __name__ == "__main__":
    n, w, h, grid, robots = parse_input()
    print(bfs(n, w, h, grid, robots))

Compilation message (stdout)

Compiling 'robots.py'...

=======
  adding: __main__.pyc (deflated 41%)

=======

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40