순간이동

시작점 a에서 도착점 b로 이동할 때 x와 y를 양방향으로 잇는 순간이동 장치를 쓸 수도 있고 안 쓸 수도 있다. 트랙터로 이동하는 최소 거리를 구한다.

쉬움2수학구현완전 탐색그리디면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

농장 일 중에서 농부 존이 가장 싫어하는 것은 소똥을 잔뜩 실어 나르는 일이다. 이 일을 줄이려고 그는 새 장치를 만들었다. 바로 거름 순간이동기다. 트랙터 뒤에 수레를 달고 두 지점 사이로 거름을 실어 나르는 대신, 순간이동기로 거름을 한 위치에서 다른 위치로 즉시 보낸다.

농부 존의 농장은 하나의 길고 곧은 도로를 따라 있어서, 농장의 모든 위치는 그 도로 위의 좌표 하나로 나타낸다(수직선 위의 점이라고 보면 된다). 순간이동기는 두 수 xxyy로 정해진다. 위치 xx로 가져온 거름은 위치 yy로 즉시 이동하고, 위치 yy로 가져온 거름은 위치 xx로 즉시 이동한다.

농부 존은 거름을 위치 aa에서 위치 bb로 옮기려 하고, 이 과정에 도움이 될지도 모르는 순간이동기를 하나 만들어 두었다. 물론 도움이 되지 않으면 쓰지 않아도 된다. 트랙터로 거름을 끌고 이동해야 하는 총 거리의 최솟값을 구하라.

입력

입력은 한 줄이며, 공백으로 구분된 네 정수 aa, bb, xx, yy가 주어진다. aabb는 각각 출발 위치와 도착 위치이고, xxyy는 순간이동기를 나타낸다. 모든 위치는 00 이상 100100 이하의 정수이며, 서로 같을 수도 있다.

출력

농부 존이 트랙터로 거름을 끌고 이동해야 하는 최소 거리를 정수 하나로 출력한다.

힌트

a=3a = 3, b=10b = 10, x=8x = 8, y=2y = 2인 경우를 보자. 거름을 위치 3에서 위치 2까지 끌고 간 다음 위치 8로 순간이동시키고, 거기서 위치 10까지 끌고 가는 것이 가장 좋다. 트랙터로 이동한 거리는 1 + 2 = 3이다.