Robots

The engineers at VRI (Voltron Robotics Institute) have built a swarm of $n$ robots. Any two compatible robots that stand on the same grid cell can merge to form a composite robot.

The robots are labeled from $1$ to $n$ ($n \le 9$). Two robots are compatible if their labels form a consecutive range. Initially, each of the $n$ robots carries one unique label. A composite robot formed by merging two or more robots is assigned two labels: the minimum and the maximum labels among the robots that merged into it.

For example, robot $2$ can only merge with robot $3$ or robot $1$. If robot $2$ merges with robot $3$, a composite robot 2-3 is formed. If robot 2-3 merges with robot 4-6, a composite robot 2-6 is formed. The robot 1-$n$ is formed once all robots have merged.

The engineers place the $n$ robots in a room made of $w \times h$ grid cells, surrounded by walls. Some cells are occluded and cannot be entered by the robots. Each cell can hold one or more robots, and a robot always occupies exactly one cell. Initially, every robot is placed on a distinct cell.

The robots are primitive. After an engineer pushes a robot, it can only move in a straight line along the x-axis or the y-axis. Once pushed in one of the four axis-parallel directions, the robot keeps moving in that direction until it is blocked by an occlusion or a wall. After the robot stops, it scans for compatible robots on the same cell and merges with any it finds into a larger robot. Merging repeats until no further merge is possible.

To help the robots change direction, the engineers place rotating plates on some cells. A plate rotates either clockwise or anti-clockwise. A robot that moves onto a cell with a rotating plate always turns its moving direction by 90 degrees in the same rotational direction as the plate. If a robot is pushed while resting on a rotating plate, it turns 90 degrees first and then moves off in a straight line, in a direction perpendicular to the direction it was pushed in.

Only one robot can move at a time.

Your task is to find the minimum number of pushes needed so that all $n$ robots are merged into one, if that is possible.

The first line contains three integers $n$, $w$, and $h$, separated by spaces.

Each of the next $h$ lines contains $w$ characters describing one row of the room. Each character represents one cell:

• A digit ('1' to '9') means a robot with that label starts on the cell.
• 'x' means the cell is occluded.
• 'A' means the cell holds a plate rotating anti-clockwise.
• 'C' means the cell holds a plate rotating clockwise.
• '.' marks every other (empty) cell.

Constraints: $n \le 9$, $w \le 500$, $h \le 500$.

Print a single line: the minimum number of pushes needed to merge all $n$ robots into one, or -1 if merging is impossible.

In the room from the first test case, the following 5 pushes merge all robots optimally:

1. Push robot 3 rightward. It moves right, reaches a rotating plate, turns anti-clockwise, and continues upward, finally stopping in front of the wall.
2. Push robot 4 upward. It moves up, stops in front of the wall, and merges with robot 3 to form robot 3-4.
3. Push robot 2 upward. It moves up, reaches a rotating plate, turns anti-clockwise, hits a wall, and stops.
4. Push robot 2 rightward. It turns anti-clockwise, moves up, stops at the corner, and merges with robot 1 to form robot 1-2.
5. Push robot 3-4 leftward. It moves left, stops at the corner, and merges with robot 1-2.