7130 : 체스 나이트 이동수
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
체스 나이트가 N × N 크기의 체스판 위에 놓여 있습니다.
나이트의 시작 좌표와 목적지 좌표가 주어질 때, 목적지까지 도달하기 위한 최소 나이트 이동 횟수를 구하십시오.
나이트의 시작 좌표와 목적지 좌표가 주어질 때, 목적지까지 도달하기 위한 최소 나이트 이동 횟수를 구하십시오.
입력 설명
첫째 줄에 N sr sc er ec 형식이 공백으로 구분되어 주어집니다. N은 체스판 한 변의 길이($4 \le N \le 100$), sr, sc는 시작 좌표, er, ec는 목적지 좌표($0$-indexed)입니다.
출력 설명
나이트의 최소 이동 횟수를 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8 0 0 7 7
출력 예시
COPY
복사되었습니다!
복사되었습니다!
6도움
가중치 없는 그래프의 최단 거리이므로 BFS 탐색을 사용해 레벨 단위로 거리를 누적하여 탐색하십시오. 나이트의 이동 벡터는 총 8가지입니다.