킹 슬라임
시간 제한8초메모리 제한512 MB
W×H 격자에 놓인 N마리의 슬라임을 벽이나 다른 슬라임에 닿을 때까지 밀어서 모두 하나로 합치는 데 필요한 최소 이동 횟수를 구합니다.
문제
W × H 크기의 격자가 벽으로 둘러싸여 있다. 격자의 일부 칸에는 슬라임이 있다. 슬라임들은 서로 합쳐 '킹 슬라임'이 되려고 한다.
한 번의 이동에서 슬라임은 동, 서, 남, 북 중 한 방향으로, 다른 슬라임이 있는 칸에 들어가거나 주변 벽에 부딪힐 때까지 움직인다. 두 슬라임이 만나면 합쳐져 새로운 슬라임이 된다.
모든 슬라임이 합쳐져 킹 슬라임이 되는 데 필요한 최소 이동 횟수를 구하는 프로그램을 작성하라. 슬라임은 한 마리씩 차례로 움직이며, 동시에 움직이지 않는다.
입력
첫째 줄에 세 정수 N, W, H가 주어진다 (2 ≤ N ≤ 40000, 1 ≤ W, H ≤ 100000). N은 슬라임의 수이고, W와 H는 격자의 너비와 높이이다.
이어지는 N개의 줄에는 각 슬라임의 초기 좌표가 주어진다. i번째 줄에는 정수 xi (1 ≤ xi ≤ W)와 yi (1 ≤ yi ≤ H)가 주어지며, 이것이 i번째 슬라임의 좌표이다. 모든 좌표는 1부터 시작한다.
처음에 각 칸에는 최대 한 마리의 슬라임만 있다고 가정할 수 있다.
출력
모든 슬라임이 합쳐져 킹 슬라임이 되는 데 필요한 최소 이동 횟수를 출력한다.