베일 도형
시간 제한1초메모리 제한1024 MB
이미 놓인 베일을 기준으로 베일을 차례로 붙여 나갈 때 노출된 겉넓이를 구합니다. 겹치는 배치가 있으면 -1을 출력합니다.
문제
소들은 건초 더미(베일)로 여러 가지 모양을 만드는 것을 좋아한다. 새 모양은 1 x 1 x 1 크기의 정육면체 베일 N개(1 ≤ N ≤ 25,000)로 만든다.
베일 1은 바닥에 놓여 있다. 베일을 놓은 뒤, 2번부터 N번까지의 베일은 이미 놓인 베일 중 하나를 기준으로 한 상대적인 위치에 놓여 도형에 붙는다. 예를 들어 다음과 같이 놓는다.
- 베일 1: 바닥에 놓는다.
- 베일 2: 베일 1의 오른쪽에 놓는다.
- 베일 3: 베일 2의 앞쪽에 놓는다.
- 베일 4: 베일 3의 앞쪽에 놓는다.
그 결과 (위아래가 뒤집힌) L자 모양이 된다.
+--+--+
1-> / / /| <-2
+--+--+ +
| / /|/
++--+ +
/ /|/ <-3
+--+ +
| |/ <-4
+--+
베일 5를 베일 1의 위에 놓으면 모양의 높이가 올라간다.
+--+
/ /|
+--+ +--+
5-> | |/ /| <-2
+--+--+ +
1-> | / /|/
++--+ +
/ /|/ <-3
+--+ +
| |/ <-4
+--+
베일 6을 베일 4의 뒤쪽에 놓으면 베일 3과 6이 겹치므로 잘못된 모양이 된다.
입력
첫 줄에 정수 N이 주어진다. 둘째 줄부터 N번째 줄까지는 각각 j X 형식으로 배치가 주어진다. j는 이미 놓인 베일의 번호이고, X는 L(왼쪽), R(오른쪽), F(앞), B(뒤), O(위), U(아래) 중 하나이다. 베일은 서로 붙여 둘 수 있으며, 빈 공간 위로 뻗어 나가더라도 아래를 받칠 것이 없어도 된다.
출력
입체의 노출된 겉넓이를 한 줄에 출력한다. 어떤 면이 다른 베일의 면과 닿지 않고 바닥에도 닿지 않으면 그 면은 노출된 것으로 본다. 바닥에 놓인 베일의 아랫면은 바닥에 닿으므로 세지 않는다. 모양이 잘못되었으면 -1을 출력한다.
베일 1에서 25베일 너비보다 멀리 놓이는 베일은 없다. 바닥 아래에 놓이는 베일은 없다.