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))
