3137 : 체스판의 나이트 이동
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 2
•통과: 2
•만든사람: suakii
문제 설명
$8 \times 8$ 체스판에서 나이트가 위치 $(r_1, c_1)$에서 위치 $(r_2, c_2)$로 이동하는 데 필요한 최소 이동 횟수를 구하는 문제입니다.
♞ 나이트의 이동 방식 (총 8가지 방향)
가운데 검은 칸(♞ 나이트)에서 한 번의 이동으로
초록색 점(● 이동 가능 칸) 중 하나로 ‘L’자 형태로 점프할 수 있습니다.
초록색 점(● 이동 가능 칸) 중 하나로 ‘L’자 형태로 점프할 수 있습니다.
체스판은 $1 \le r, c \le 8$ 크기이며, 나이트는 장애물에 상관없이 한 번에 직진 2칸 + 꺾어서 1칸(또는 직진 1칸 + 꺾어서 2칸)으로 이동합니다. 즉, 현재 좌표를 $(r, c)$라 할 때 다음 8가지 위치 중 체스판을 벗어나지 않는 곳으로 이동할 수 있습니다:
- $(r-2, c-1)$, $(r-2, c+1)$
- $(r-1, c-2)$, $(r-1, c+2)$
- $(r+1, c-2)$, $(r+1, c+2)$
- $(r+2, c-1)$, $(r+2, c+1)$
[제약 조건]
• $1 \le r_1, c_1, r_2, c_2 \le 8$
• 모든 좌표는 정수
입력 설명
첫째 줄에 시작 위치 $r_1, c_1$이 공백으로 구분되어 주어집니다.
둘째 줄에 목표 위치 $r_2, c_2$가 공백으로 구분되어 주어집니다.
둘째 줄에 목표 위치 $r_2, c_2$가 공백으로 구분되어 주어집니다.
출력 설명
최소 이동 횟수를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1 1
2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1