메뉴 건너뛰기

문제

00c20 체스판의 기사 0  

시간메모리제출 올바른 답 비율
1초64MB
88
18
20.5%


나의 횟수나의 최근 판정시도 성공 비율
1713
76.5%
체스판의 기사  

\(8 \times 8\) 체스판이 다음의 그림과 같이 주어질 때, 임의의 한 지점을 2개의 숫자로 나타낼 수 있다. 그림의 A 지점은 (4, 2)이고, B 지점은 (7, 5)이다.

체스판의 ‘기사’는 다음의 그림과 같이 L자 형태로 움직인다. 즉, 기사가 K 위치 (4, 4)에 있을 때 기사가 1회의 이동으로 A, B, C, D, E, F, G, H 중에 한 위치로 갈 수 있다.

\(N \times N\) 체스판에서 기사의 현재 위치와 목표 위치가 주어질 때, 현재 위치에서 목표 위치로 이동하는데 필요한 가장 적은 이동수를 출력하는 프로그램을 작성하시오.

입력

입력 파일은 세 개의 줄로 이루어진다. 첫 번째 줄에 체스판의 크기를 나타내는 정수 \(N (8 \leq N \leq 100)\) 이 주어진다. 두 번째 줄에 기사의 현재 위치를 나타내는 한 쌍의 정수가 주어진다. 세 번째 줄에 기사의 목표 위치를 나타내는 한 쌍의 정수가 주어진다. 기사의 현재 위치와 목표 위치를 나타내는 정수의 범위는 1~\(N\) 이다.

출력

출력 파일의 첫 번째 줄에 기사를 현재 위치에서 목표 위치로 이동하기 위한 ‘최소 이동수’를 출력한다. 단, 체스판을 벗어나는 이동은 허용되지 않는다.

예시
1입력
8
2 1
3 3
출력
1
2입력
8
4 2
7 5
출력
2
위로