시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 642 | 195 | 155 | 30.754% |
상근이는 생일 선물로 장난감 탱크 N개를 받았다. 탱크를 가지고 놀기 전장을 만들었다. 전장은 나무판 위에 N행 N열 크기로 만들었다.
각 탱크가 한 번에 움직일 수 칸은 인접한 네 칸이다. 탱크는 같은 행과 열에 있는 모든 칸을 공격할 수 있다. 따라서, 탱크는 자신이 있는 칸에 해당하는 행과 열을 보호하고 있다고 말할 수 있다.
두 탱크가 동시에 같은 정사각형 안에 있을 수는 없다.
이렇게 탱크를 가지고 두~세시간 동안 열심히 놀고 있었다. 상근이의 어머니는 점심까지 거르면서 놀고있는 상근이를 못마땅하게 생각했고, 당장 점심을 먹으러 오라고 소리쳤다. 상근이는 탱크가 모든 행과 열을 보호하게 배치를 바꾼 다음에 점심을 먹으러 가려고 한다. (즉, 각각의 행과 열에 하나의 탱크만 있어야 한다)
이렇게 배치를 바꾸는 경우에 탱크를 움직이는 횟수를 적게 하려고 한다.
탱크를 몇 번 움직이면, 각 행과 열에 있는 탱크가 하나가 되는지 구하는 프로그램을 작성하시오. 움직이는 방법이 여러 가지라면 탱크를 움직이는 횟수가 가장 작은 것을 찾는다.
첫째 줄에 탱크의 수 N이 주어진다. (5 ≤ N ≤ 500)
다음 N개 줄에는 각 탱크가 있는 행의 번호 R과 열의 번호 C가 주어진다. (1 ≤ R, C ≤ N) 행과 열은 1부터 N까지 번호가 매겨져 있으며, 위에서 아래, 왼쪽에서 오른쪽 순서이다. 두 탱크가 같은 칸에 있는 경우는 없다.
첫째 줄에 탱크를 몇 번 이동시키면 되는지를 출력한다. 이 값을 K라고 한다.
다음 K개 줄에는 어떤 탱크를 어느 방향으로 움직이는지 출력한다. 가장 먼저 주어지는 탱크의 번호는 1번이고, 나머지 탱크는 순서대로 2, 3, ..., N번이다. 방향은 왼쪽으로 이동할 때는 'L', 오른쪽은 'R', 위는 'U', 아래는 'D'로 출력한다.
정답은 여러 가지일 수도 있다.
5 1 1 1 2 1 3 1 4 1 5
10 1 D 2 D 3 D 4 D 1 D 2 D 3 D 1 D 2 D 1 D
5 2 3 3 2 3 3 3 4 4 3
8 1 R 1 R 2 U 2 U 4 D 4 D 5 L 5 L
6 1 1 1 2 2 1 5 6 6 5 6 6
8 2 R 2 D 3 D 3 R 4 U 4 L 5 L 5 U
Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 4번