Kings
시간 제한1초메모리 제한512 MB
n x n 체스판에 놓인 n개의 킹을 주대각선 위로 모두 옮기는 데 필요한 최소 이동 횟수를 구한다. 한 번의 이동으로 킹 하나를 가로 또는 세로로 한 칸 움직인다.
문제
여러 개의 king 말이 뒤섞여 있는 체스판에서 "체스판 정리하기" 게임이 시작된다. 플레이어는 모든 말을 검은 칸으로 이루어진 주대각선을 따라 한 줄로 나란히 놓아야 한다.
일반 체스와 달리, 한 번의 이동에서는 king 하나를 가로 또는 세로 방향 중 한 방향으로만 이웃한 빈 칸으로 한 칸 옮긴다.
게임이 주어졌을 때, 게임을 끝내는 데 필요한 최소 이동 횟수를 구한다.
그림 K.1: 예제 입력 2에 대한 그림. 이 경우 모든 king을 검은 대각선을 따라 놓는 데 필요한 최소 이동 횟수는 그림과 같이 28이다.
입력
- 행과 열의 개수 n이 주어지는 한 줄 (1 ≤ n ≤ 500).
- 그다음 n개의 줄에는 king 하나의 위치를 나타내는 2차원 정수 좌표 c와 r이 주어진다 (1 ≤ c, r ≤ n).
모든 king은 서로 다른 위치에서 시작한다.
출력
king으로 주대각선(r = c)을 모두 채우는 데 필요한 최소 이동 횟수를 출력한다.