기사의 마라톤

시간 제한2초메모리 제한512 MB

요약

아주 큰 직사각형 체스판에서 시작 칸에서 목표 칸까지 나이트가 판을 벗어나지 않고 이동하는 최소 횟수를 구한다.

난이도: 어려움10점 중 8점
유형: 수학, BFS, 그리디, 기하
정답자: 아직 제출이 없습니다

문제

길고 긴 전투 끝에 침공군이 물러났다. 왕은 살아남은 단 한 명의 기사를 수도로 보내 승리를 알리려 한다. 아주 먼 여정이 될지도 모른다.

기사는 체스판의 나이트처럼 움직인다. 한 번 움직일 때 동서남북 네 방향 중 하나로 두 칸 간 다음, 그 방향과 직각으로 한 칸 더 간다. 여정 내내 기사는 새로운 전쟁을 일으키지 않도록 왕국 안에 머물러야 한다. 왕국은 $NX \times NY$ 크기의 직사각형 격자이고, 전투가 벌어진 $8 \times 8$ 판보다 훨씬 클 수도 있다. 행과 열의 번호는 0부터 매긴다. 기사는 칸 $(KX, KY)$ 에서 출발해 수도인 칸 $(CX, CY)$ 까지 가야 한다. 기사가 수도에 도착하는 데 필요한 최소 이동 횟수를 구한다.

나이트가 한 번에 갈 수 있는 칸

그림 1: 기사가 한 번에 갈 수 있는 칸.

입력

입력은 세 줄이고, 각 줄에 정수가 두 개씩 주어진다.

첫째 줄에는 왕국의 크기 $NX$ , $NY$ 가 주어진다. ( $8 \le NX, NY \le 10^9$ )
둘째 줄에는 기사의 출발 위치 $KX$ , $KY$ 가 주어진다. ( $0 \le KX < NX$ , $0 \le KY < NY$ )
셋째 줄에는 수도의 위치 $CX$ , $CY$ 가 주어진다. ( $0 \le CX < NX$ , $0 \le CY < NY$ )

출력

기사가 수도까지 가는 데 필요한 최소 이동 횟수를 한 줄에 출력한다.

예제3

예제 1
입력
```
8 8
0 0
7 7
```
예상 출력
```
6
```
예제 2
입력
```
1000 7000
253 6789
253 6789
```
예상 출력
```
0
```
예제 3
입력
```
8 1000000000
3 3
3 999999999
```
예상 출력
```
499999998
```