VRI (Voltron Robotics Institute)의 한 공학자가 공학자가 n 개의 로봇을 만들었다. 이 로봇들 은 결합할 수 있는 두 로봇이 같은 격자 (위치 )에 있게 되면 하나로 합쳐져서 다른 형태의 결합 로봇이 된다 . 로봇들은 1부터 n (n ≤ 9) 까지 각각 번호가 매겨져 있다. 만약 두 로봇이 서로 연속된 번호를 가지고 있으면 이 로봇들은 서로 결합할 수 있다. 처음에는 모든 n 개의 로봇들이 모두 서로 다른 번호를 가지고 있다 . 둘 혹은 그 이상의 로봇이 합쳐진 결합 로봇은 결합 로봇을 구성하는 로봇들의 최소번호와 최대번호로 이루어진 두 개의 번호로 나타낸다.
예를 들어 , 2번 로봇은 3번 로봇이나 1번 로봇과만 합쳐질 수 있다 . 만약 , 2번 로봇이 3번 로봇과 합쳐지면, 2-3 결합로봇이 된다 . 2-3 결합 로봇이 4-6 결합로봇과 합쳐지면 2-6 결합로봇이 된다 . 모든 로봇이 합쳐지면 1-n 결합로봇이 된다 .
이 n 개의 로봇들이 벽으로 둘러 쌓인 w × h 크기의 격자로 된 방에 놓여있다 . 일부 격자들은 막혀있고 , 이 곳으로는 로봇이 움직일 수 없다 . 하나의 격자에는 하나 혹은 그 이상의 로봇이 있을 수 있으며 , 로봇 들은 하나의 격자에만 있을 수 있다. 처음에는 , 모든 로봇은 서로 다른 격자에 위치하고 있다 .
이 로봇들은 상당히 초보적인 단계이다. 사람이 로봇들을 밀면 x-축 혹은 y-축에 따라 평행하게 직선으로만 움직일 수 있다 . x-축 혹은 y-축에 따라 평행하게 움직일 수 있는 네 방향중의 하나로 로봇을 밀면, 로봇은 벽을 만나거나 막혀있는 격자를 만날 때까지 로봇은 로봇을 민 방향으로 계속 움직인다 . 로봇이 움직임을 멈추고 나면 , 같은 격자에 합쳐질 수 있는 로봇이 있는지를 찾고, 그것들과 결합하여 더 큰 로봇이 된다. 결합 과정은 더 이상 결합할 수 있는 로봇이 없을 때까지 진행된다 .
로봇이 방향을 바꾸는 것을 가능하게 하기 위해 , 일부 격자에는 회전판이 설치되어 있다 . 회전판은 시계 방향 혹은 반 시계방향으로 시계방향으로 회전 할 수 있다. 회전판이 있는 격자에 도달한 로봇은 회전판의 회전방향으로 90 도 회전하여 이동방향을 바꾼다 . 만약 로봇이 회전판 위에서 멈추어있을 때 다시 미는 경우에는 먼저 90 도 회전을 한 후에 회전한 방향으로 움직이게 된다 .
한번에 하나의 로봇만 움직일 움직일 수 있다.여러분이 해야 할 일은 모든 n 개의 로봇을 하나로 결합하도록 하는 (가능하다면 ) 로봇을 미는 최소 횟수를 구하는 것이다.
입력 4 10 5 1......... AA...x4... ..A..x.... 2....x.... ..C.3.A... 출력 5[예제 입출력 에 대한 설명 ] 다음의 5번의 단계로 단계로 최적으로 최적으로 로봇들을 로봇들을 결합할 수 있다 .
출처:apio2013