문제
N x N 보드에 보드에서 다음과 같은 게임을 하고자 한다.
게임 규칙은 다음과 같다.
* 총 N개의 탱크가 있다. 탱크의 초기 위치는 정해진다.
* N개의 탱크는 상하좌우로 움직일 수 있다.
* 한 칸에 2개의 탱크가 있는 경우는 없다.
게임의 규칙을 지키면서 N x N 보드에 각 행과 열에 위치한 탱크가 하나씩만 존재하게 하고자 할 때, 최소의 이동횟수를 구하는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 1 이상 500 이하의 정수 N이 입력된다.
N개의 줄에는 각 탱크의 행과 열의 좌표 R, C (1≤R, C≤ N)이 입력된다.
출력
탱크를 행과 열에 하나씩만 위치하게 하기 위해서 필요한 최소 이동횟수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 30점 | |
| #3 | 50점 | 추가 제한 없음 |
예제1
입력
5
11
12
13
14
15
출력
10
출처
COCI 2006/2007 Contest #3 4번