케익배달 > 문제은행



실전대비 Level7

1676 : 케익배달

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 12 회    시도횟수: 30 회   



호동이는 자신이 만든 케익을 고객들에게 직접배달을 하려고 한다.
N명의 고객에게 케익을 배달하는데 주문이 들어온 순서대로 배달하기를 원하며 

고객이 케익을 받을 수 있을 만큼 충분히 가까이까지 배달한다.

 

N명의 고객의 위치는 순서대로 100 x 100 격자의 정수좌표로 주어지고 처음 출발하는 위치도 정수좌표로 주어진다. 

호동이는 격자위에서 상, 하, 좌, 우로만 움직이며 

고객에게 케익을 전달하기 위해서는 그 고객의 위치까지 가거나 고객의 상, 하, 좌, 우의 인접격자점에 가야한다. 

이때 호동이가 최단 거리를 이동하여 배달을 끝낼 수 있는 거리를 계산하는 프로그램을 작성하시오. 

 

여기서 거리는 격자상의 칸 수를 말한다.

 

 

07f1ee470c4ca420b78cf86b19196679_1450334
 

 

위의 예에서 호동이는 11칸을 움직여서 세명의 고객에게 배달을 다 할 수 있다. 

호동이는 반드시 고객들에게 순서대로 배달을 하며 

순서에 어긋난 사람에게 배달을 할 수 있는 위치에 있더라도 케익을 주지 않고 순서대로 배달을 한다. 

고객의 위치는 중복이 될 수도 있다




입력의 첫째 줄에 N이 주어지고 둘째 줄에는 호동이가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 주어진다. 모든 위치의 좌표(X ,Y)는 X와 Y사이에 공백이 한 칸 주어진다.
(1≤N, X, Y≤100 )




최단거리를 한 줄에 출력한다.



3
2 2 
3 6 
3 7 
7 3
11



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.