로봇 Batch 컴파일 명령

VRI (Volton 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$?축에 따라 평행하게 직선으로만 움직일 수 있다. $x$?축 혹은 $y$?축에 따라 평행하게 움직일 수 있는 네 방향중의 하나로 로봇을 밀면, 로봇은 벽을 만나거나 막혀있는 격자를 만날 때까지 로봇은 로봇을 민 방향으로 계속 움직인다. 로봇이 움직임을 멈추고 나면, 같은 격자에 합쳐질 수 있는 로봇이 있는지를 찾고, 그것들과 결합하여 더 큰 로봇이 된다. 결합 과정은 더 이상 결합할 수 있는 로봇이 없을 때까지 진행된다.

로봇이 방향을 바꾸는 것을 가능하게 하기 위해, 일부 격자에는 회전판이 설치되어 있다. 회전판은 시계방향 혹은 반 시계방향으로 회전할 수 있다. 회전판이 있는 격자에 도달한 로봇은 회전판의 회전방향으로 90도 회전하여 이동방향을 바꾼다. 만약 로봇이 회전판 위에서 멈추어있을 때 다시 미는 경우에는 먼저 90도 회전을 한 후에 회전한 방향으로 움직이게 된다.

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

여러분이 해야 할 일은 모든 $n$개의 로봇을 하나로 결합하도록 하는 (가능하다면) 로봇을 미는 최소 횟수를 구하는 것이다.

입력 형식

표준입력으로부터 다음의 데이터를 읽는다. 입력의 첫 번째 줄에는 세 정수 $n$, $w$, $h$가 빈칸을 사이에 두고 주어진다. 그 다음 $h$개의 줄에는 각 줄마다 $w$개의 문자가 주어지는데, 이것은 방의 상황을 나타낸다. $w \times h$개 문자의 각각은 하나의 격자를 의미한다.

숫자 ('1'부터 '9')는 그 숫자가 있는 곳의 격자에 존재하면서, 그 숫자를 번호로 하는 로봇을 나타낸다. 문자 ‘x’는 로봇이 지나갈 수 없는 격자 위치를 나타낸다. 문자 'A' 와 'C'는 그 격자에서의 회전판을 나타내며, 'A'는 회전판이 반 시계방향으로 회전함을 나타내며, 'C'는 시계방향으로 회전함을 나타낸다. 그 외 모든 다른 격자들은 문자 '.'으로 나타낸다.

출력 형식

출력은 표준출력을 사용한다. 모든 $n$개의 로봇이 하나로 결합하도록 하는 로봇을 미는 최소 횟수를 하나의 정수로 출력한다. 만약, 모든 $n$개의 로봇을 하나로 결합하는 것이 불가능하면 $?1$을 출력한다.

서브태스크

여러분의 프로그램은 다음과 같은 네 가지 조건의 테스트 데이터 세트로 테스트 된다:

1. (10점) $n = 2$, $w \le 10$, $h \le 10$, 회전판이 없음.
2. (20점) $n = 2$, $w \le 10$, $h \le 10$
3. (30점) $n \le 9$, $w \le 300$, $h \le 300$
4. (40점) $n \le 9$, $w \le 500$, $h \le 500$

예제

입력

4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

출력

5

다음의 5번의 단계로 최적으로 로봇들을 결합할 수 있다.

1. 로봇 3을 오른쪽으로 민다. 로봇 3은 오른쪽으로 움직이다가 회전판을 만나고, 반 시계방향으로 90도 방향을 바꾸어서 위로 계속 움직인다. 로봇은 벽을 만나면 정지한다.
2. 로봇 4를 위쪽 방향으로 민다. 로봇은 위쪽으로 움직이다가 벽을 만나면 정지하고, 3번 로봇과 결합하여 3-4 로봇이 된다.
3. 로봇 2를 위쪽 방향으로 민다. 로봇은 위쪽으로 움직이다가 회전판을 만나고, 반 시계방향으로 회전한 후 바로 벽을 만나 멈춘다.
4. 로봇 2를 위쪽 방향으로 민다. 로봇은 반 시계방향으로 회전하고, 위쪽으로 움직여 구석에서 멈춘 다음 로봇 1과 결합하여 1-2 로봇이 된다.
5. 로봇 3-4를 왼쪽으로 민다. 로봇은 왼쪽으로 움직여 구석에 멈춘 후 1-2 로봇과 결합한다.