로봇

VRI(Voltron Robotics Institute)의 엔지니어들이 $n$개의 로봇으로 이루어진 군집을 만들었다. 같은 칸에 있는 서로 호환되는 두 로봇은 합쳐져 하나의 합성 로봇이 될 수 있다.

로봇에는 $1$부터 $n$까지의 번호가 붙어 있다($n \le 9$). 두 로봇은 번호가 연속일 때 호환된다. 처음에 $n$개의 로봇은 각각 서로 다른 하나의 번호를 가진다. 두 개 이상의 로봇이 합쳐져 만들어진 합성 로봇에는 합쳐진 로봇들의 최소 번호와 최대 번호, 두 개의 번호가 부여된다.

예를 들어 로봇 $2$는 로봇 $3$ 또는 로봇 $1$하고만 합쳐질 수 있다. 로봇 $2$가 로봇 $3$과 합쳐지면 합성 로봇 2-3이 만들어진다. 합성 로봇 2-3이 합성 로봇 4-6과 합쳐지면 합성 로봇 2-6이 만들어진다. 모든 로봇이 합쳐지면 로봇 1-$n$이 만들어진다.

엔지니어들은 $n$개의 로봇을 벽으로 둘러싸인 $w \times h$ 칸짜리 방에 놓는다. 일부 칸은 막혀 있어 로봇이 들어갈 수 없다. 각 칸에는 하나 이상의 로봇이 있을 수 있고, 로봇은 항상 정확히 한 칸을 차지한다. 처음에 모든 로봇은 서로 다른 칸에 놓인다.

로봇은 단순하다. 엔지니어가 로봇을 밀면, 로봇은 x축 또는 y축을 따라 직선으로만 움직인다. 축에 평행한 네 방향 중 하나로 밀리면, 로봇은 막힌 칸이나 벽에 가로막힐 때까지 그 방향으로 계속 이동한다. 멈춘 뒤에는 같은 칸에 있는 호환되는 로봇을 찾아, 있으면 합쳐져 더 큰 로봇이 된다. 이 합체는 더 이상 합칠 수 없을 때까지 반복된다.

로봇의 방향 전환을 돕기 위해, 엔지니어들은 일부 칸에 회전판을 놓는다. 회전판은 시계 방향 또는 반시계 방향으로 돈다. 회전판이 있는 칸으로 이동해 들어온 로봇은 항상 이동 방향을 회전판과 같은 방향으로 90도 꺾는다. 회전판 위에 놓인 상태에서 밀리면, 로봇은 먼저 90도 회전한 뒤, 밀린 방향과 수직인 방향으로 직선 이동을 시작한다.

한 번에 한 로봇만 움직일 수 있다.

목표는 모든 $n$개의 로봇을 하나로 합치는 데 필요한 최소 밀기 횟수를 구하는 것이다(가능한 경우).

첫 번째 줄에 세 정수 $n$, $w$, $h$가 공백으로 구분되어 주어진다.

이어지는 $h$개의 줄에는 각각 방의 한 행을 나타내는 $w$개의 문자가 주어진다. 각 문자는 한 칸을 의미한다.

• 숫자('1'부터 '9')는 그 번호의 로봇이 해당 칸에서 시작함을 뜻한다.
• 'x'는 막힌 칸을 뜻한다.
• 'A'는 반시계 방향으로 도는 회전판이 있는 칸을 뜻한다.
• 'C'는 시계 방향으로 도는 회전판이 있는 칸을 뜻한다.
• '.'는 그 밖의 빈 칸을 뜻한다.

제약: $n \le 9$, $w \le 500$, $h \le 500$.

모든 $n$개의 로봇을 하나로 합치는 데 필요한 최소 밀기 횟수를 한 줄에 출력한다. 합치는 것이 불가능하면 -1을 출력한다.

첫 번째 테스트 케이스의 방에서는 다음 5번의 밀기로 모든 로봇을 최적으로 합칠 수 있다.

1. 로봇 3을 오른쪽으로 민다. 로봇은 오른쪽으로 이동하다 회전판을 만나 반시계 방향으로 꺾여 위로 계속 이동하고, 결국 벽 앞에서 멈춘다.
2. 로봇 4를 위로 민다. 로봇은 위로 이동해 벽 앞에서 멈추고, 로봇 3과 합쳐져 로봇 3-4가 된다.
3. 로봇 2를 위로 민다. 로봇은 위로 이동하다 회전판을 만나 반시계 방향으로 꺾이고, 벽에 부딪혀 멈춘다.
4. 로봇 2를 오른쪽으로 민다. 로봇은 반시계 방향으로 꺾여 위로 이동하고, 모서리에서 멈춰 로봇 1과 합쳐져 로봇 1-2가 된다.
5. 로봇 3-4를 왼쪽으로 민다. 로봇은 왼쪽으로 이동해 모서리에서 멈추고, 로봇 1-2와 합쳐진다.