VRI (Voltron Robotics Institute)의 기술자들은 n개의 로봇들을 만들었다. 로봇들은 각각 고유의 번호( 1 ≤ n ≤ 9)를 가지고 있으며 이차원 평면 격자의 같은 위치에 두 개의 로봇이 위치하는 경우 하나의 로봇으로 합성된다. 합성되는 두 로봇의 번호는 연속한 번호의 로봇이어야 하며 움직임이 멈춘 경우이다. 또한 합성된 로봇의 번호는 합성되는 로봇의 최솟값 번호와 최댓값 번호를 동시에 갖게 된다. 예를 들면 2번 로봇은 1번 로봇과 합성될 수 있으며 합성된 로봇의 번호는 1-2가 된다. 다른 예로 2번 로봇은 3번 로봇과도 합성될 수 있는데 이때 합성된 로봇의 번호는 2-3이 된다. 합성된 로봇 2-3과 합성된 로봇 4-6이 합성될 수 있는데 이 때 새롭게 합성된 로봇의 번호는 2-6이 된다. 이렇게 로봇들을 합성하게 되면 결국 1-n 로봇 하나만 남겨질 수 있다.

 

로봇들은 원시적인 방법으로만 움직이게 되는데 w×h 크기의 이차원 격자에서 x축의 좌우 방향과 y축의 상하 방향으로만 움직인다. 로봇은 엔지니어가 원하는 방향으로 로봇을 밀어야 움직이는데 한 번 움직인 로봇은 격자의 테두리나 격자 내부의 벽을 만난 경우 멈춘다. 지나가는 길에 다른 로봇이 정지해 있는 경우 그냥 지나쳐 갈 수 있다.

 

로봇의 움직임이 너무 단조롭다고 생각한 기술자들은 로봇이 움직일 때 방향전환을 돕기 위하여 이차원 격자 곳곳에 두 종류의 회전판을 설치하였다. 하나는 시계방향으로 90도 회전하는 회전판이고 다른 하나는 반시계방향으로 90도 회전하는 판이다. 회전판에 로봇이 도달 하면 90도 회전한 후 방향을 바꾸어 계속 움직이지만 이차원 격자의 테두리나 벽을 만나면 멈춘다. 회전판 위에서 밀면 회전을 먼저 한 후 이동을 한다(즉, 원하는 방향으로 로봇을 보낼 수 있다).

 

기술자는 n개의 로봇을 움직일 때 한 번에 하나의 로봇만 선택하여 이차원 격자의 상하좌우 한 방향으로만 밀어서 움직이게 할 수 있다.

입력의 첫 행에는 로봇의 개수를 나타내는 n, 이차원 격자의 가로 크기를 나타내는 w, 세로 크기를 나타내는 h, 가 공백으로 구분하여 주어진다. 두 번째 행부터 이차원 격자의 정보가 h행에 걸쳐 주어진다. 이차원 격자 내부에 대한 정보는 다음과 같다.   ‘.’ : 로봇이 움직일 수 있는 공간이다.   ‘1’ ~ ‘9’ : 로봇이 있는 공간으로 각 로봇의 고유 번호이다.   ‘A' : 로봇을 만날 경우 90도 반시계방향으로 방향을 바꾸어 계속 움직이도록 한다.   ‘C’ : 로봇을 만날 경우 90도 시계방향으로 방향을 바꾸어 계속 움직이도록 한다.   ‘x' : 이차원 내부의 벽으로 로봇이 이 벽을 만나면 멈춘다. <서브테스크> 1. n = 2, w ≤ 10, h ≤ 10 이며 회전판이 존재하지 않는다. 2. n = 2, w ≤ 10, h ≤ 10 이다. 3. n ≤ 9, w ≤ 300, h ≤ 300 이다. 4. n ≤ 9, w ≤ 500, h ≤ 500 이다.

n개의 로봇을 모두 합성하여 1개의 로봇으로 만들 수 있는 경우 최소시간을 하나의 정수로 출력한다. 만들 수 없는 경우 -1을 출력한다.

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

5

아래 5단계를 거치면 하나의 로봇으로 합성된다. 아래 그림 참고 1. 3번 로봇(5,5)을 오른쪽으로 민다. 회전판(5,7)을 만나 시계반대방향으로 90도 회전한 후, 위쪽으로 계속 움직이고 4번 로봇을 그냥 지나쳐 위쪽 테두리(1,7)에서 멈춘다. 2. 4번 로봇(2,7)을 위쪽으로 민다. 위쪽 테두리(1,7)에서 멈추고 3번 로봇과 합성되어 3-4번 로봇이 된다. 3. 2번 로봇(4,2)을 위쪽으로 민다. 회전판(2,1)을 만나 시계반대방향으로 90도 회전한 후, 왼쪽 테두리(2,1)를 보고 멈춘다. 4. 2번 로봇(2,1)을 오른쪽으로 민다. 회전판(2,1) 위이므로 시계반대방향으로 90도 회전한 후, 위쪽으로 움직이고 테두리(1,1)를 만나 멈춘다. 1번 로봇과 합성되어 1-2번 로봇이 된다. 5. 합성로봇 3-4(1,7)를 왼쪽으로 민다. 테두리(1,1)를 만나 멈추고 1-2번 합성로봇과 합성되어 1-4번 합성로봇이 된다.