Submission #998526

#	Time	Username	Problem	Language	Result	Execution time	Memory
998526		Ibrohim0704	Robots (APIO13_robots)	Pypy 3	0 / 100	1563 ms	21296 KiB

robots

from collections import deque

def parse_input():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    w = int(data[1])
    h = int(data[2])
    grid = [list(data[i + 3]) for i in range(h)]
    
    return n, w, h, grid

def get_initial_positions(grid):
    positions = {}
    for y, row in enumerate(grid):
        for x, cell in enumerate(row):
            if cell.isdigit():
                positions[int(cell)] = (y, x)
    return positions

def is_within_bounds(x, y, w, h):
    return 0 <= x < w and 0 <= y < h

def move_robot(y, x, dy, dx, grid, w, h):
    while is_within_bounds(x + dx, y + dy, w, h) and grid[y + dy][x + dx] != 'x':
        y += dy
        x += dx
        if grid[y][x] == 'A':
            dy, dx = -dx, dy
        elif grid[y][x] == 'C':
            dy, dx = dx, -dy
    return y, x

def bfs(n, w, h, grid, positions):
    initial_state = (tuple(sorted(positions.items())), 0)
    queue = deque([initial_state])
    visited = set([tuple(sorted(positions.items()))])
    
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right
    
    while queue:
        current_state, pushes = queue.popleft()
        current_positions = dict(current_state)
        
        # Check if all robots are merged
        if len(current_positions) == 1 and 1 in current_positions:
            return pushes
        
        for robot in current_positions:
            y, x = current_positions[robot]
            
            for dy, dx in directions:
                new_y, new_x = move_robot(y, x, dy, dx, grid, w, h)
                new_positions = current_positions.copy()
                new_positions[robot] = (new_y, new_x)
                
                # Perform merging of robots on the same grid
                merged_positions = {}
                for label, (my, mx) in new_positions.items():
                    if (my, mx) not in merged_positions:
                        merged_positions[(my, mx)] = []
                    merged_positions[(my, mx)].append(label)
                
                next_positions = {}
                for pos, labels in merged_positions.items():
                    merged_label = (min(labels), max(labels))
                    next_positions[merged_label] = pos
                
                next_state = tuple(sorted(next_positions.items()))
                if next_state not in visited:
                    visited.add(next_state)
                    queue.append((next_state, pushes + 1))
    
    return -1

def main():
    n, w, h, grid = parse_input()
    initial_positions = get_initial_positions(grid)
    result = bfs(n, w, h, grid, initial_positions)
    print(result)

if __name__ == "__main__":
    main()

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