| 체스판의 기사 |
|---|
\(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 | ||