순간이동
면접 대비시간 제한2초메모리 제한512 MB
시작점 a에서 도착점 b로 이동할 때 x와 y를 양방향으로 잇는 순간이동 장치를 쓸 수도 있고 안 쓸 수도 있다. 트랙터로 이동하는 최소 거리를 구한다.
문제
농장 일 중에서 농부 존이 가장 싫어하는 것은 소똥을 잔뜩 실어 나르는 일이다. 이 일을 줄이려고 그는 새 장치를 만들었다. 바로 거름 순간이동기다. 트랙터 뒤에 수레를 달고 두 지점 사이로 거름을 실어 나르는 대신, 순간이동기로 거름을 한 위치에서 다른 위치로 즉시 보낸다.
농부 존의 농장은 하나의 길고 곧은 도로를 따라 있어서, 농장의 모든 위치는 그 도로 위의 좌표 하나로 나타낸다(수직선 위의 점이라고 보면 된다). 순간이동기는 두 수 와 로 정해진다. 위치 로 가져온 거름은 위치 로 즉시 이동하고, 위치 로 가져온 거름은 위치 로 즉시 이동한다.
농부 존은 거름을 위치 에서 위치 로 옮기려 하고, 이 과정에 도움이 될지도 모르는 순간이동기를 하나 만들어 두었다. 물론 도움이 되지 않으면 쓰지 않아도 된다. 트랙터로 거름을 끌고 이동해야 하는 총 거리의 최솟값을 구하라.
입력
입력은 한 줄이며, 공백으로 구분된 네 정수 , , , 가 주어진다. 와 는 각각 출발 위치와 도착 위치이고, 와 는 순간이동기를 나타낸다. 모든 위치는 이상 이하의 정수이며, 서로 같을 수도 있다.
출력
농부 존이 트랙터로 거름을 끌고 이동해야 하는 최소 거리를 정수 하나로 출력한다.
힌트
, , , 인 경우를 보자. 거름을 위치 3에서 위치 2까지 끌고 간 다음 위치 8로 순간이동시키고, 거기서 위치 10까지 끌고 가는 것이 가장 좋다. 트랙터로 이동한 거리는 1 + 2 = 3이다.