크레인
시간 제한1초메모리 제한128 MB
두 개씩 공이 든 N개의 상자를 크레인 명령으로 조작해 흰 공 상자와 검은 공 상자가 각각 한 구간에 모이도록 만드는 최단 명령열을 구하는 문제입니다.
문제
왼쪽에서 오른쪽으로 N개의 열린 박스가 일렬로 놓여 있다. 각 박스에는 공이 정확히 두 개 들어 있으며, 각 공의 색은 흰색 또는 검은색이다.
처음에 크레인은 가장 왼쪽 박스 위에 있다. 크레인은 다음 명령으로 조작한다.
- LIJEVO: 크레인을 왼쪽의 인접한 박스로 옮긴다.
- DESNO: 크레인을 오른쪽의 인접한 박스로 옮긴다.
- UZMI BIJELU: 현재 박스에서 흰색 공 하나를 집어 든다.
- UZMI CRNU: 현재 박스에서 검은색 공 하나를 집어 든다.
- SPUSTI BIJELU: 현재 박스에 흰색 공 하나를 내려놓는다.
- SPUSTI CRNU: 현재 박스에 검은색 공 하나를 내려놓는다.
크레인은 동시에 최대 두 개의 공만 들 수 있다. 각 박스에 들어갈 수 있는 공의 개수에는 제한이 없다.
모든 공이 다음 조건을 만족하면 정렬되었다고 한다.
- 각 박스에는 같은 색의 공이 정확히 두 개 들어 있다.
- 흰색 공 두 개가 들어 있는 두 박스 사이에는 검은색 공 두 개가 들어 있는 박스가 없다.
- 검은색 공 두 개가 들어 있는 두 박스 사이에는 흰색 공 두 개가 들어 있는 박스가 없다.
공을 정렬하는 데 필요한 명령의 최소 길이 명령열을 출력하라.
출력하는 모든 명령은 실제로 수행 가능해야 한다. 예를 들어, 크레인은 가장 왼쪽 박스에서 더 왼쪽으로 이동할 수 없고, 공을 세 개 이상 들 수 없다.
입력
첫째 줄에 정수 N이 주어진다. 2 ≤ N ≤ 500.
둘째 줄에는 각 박스의 내용을 나타내는 문자열 N개가 왼쪽부터 오른쪽 순서로 주어진다.
각 문자열은 길이가 2이고, 각 문자는 B 또는 C이다. B는 흰색 공, C는 검은색 공을 뜻한다.
출력
모든 명령을 한 줄에 하나씩 출력한다.
최소 길이의 명령열이 여러 개일 수 있지만, 입력은 항상 정렬 가능한 경우만 주어진다.