나이트의 최소 이동
실버 I의견: 0
\(L \times L\) 크기의 체스판이 있다. 행과 열은 각각 \(0\)부터 \(L-1\)까지 번호가 매겨져 있으며, 칸은 \((r, c)\)로 나타낸다.
체스의 나이트(knight) 는 한 번에 다음 \(8\)가지 방향 중 하나로 이동할 수 있다. 현재 칸 \((r, c)\)에서 \((r \pm 1, c \pm 2)\) 또는 \((r \pm 2, c \pm 1)\) 중 체스판 안에 있는 칸으로 이동한다.
시작 칸 \((r_1, c_1)\)에서 목표 칸 \((r_2, c_2)\)까지 나이트가 이동하는 데 필요한 최소 이동 횟수를 구하여라. \(L \ge 4\)이므로 항상 도달할 수 있다.
\(4 \le L \le 300\), \(0 \le r_1, c_1, r_2, c_2 \le L-1\).
첫째 줄에 체스판의 크기 \(L\)이 주어진다.
둘째 줄에 시작 칸의 좌표 \(r_1\), \(c_1\)이 공백으로 구분되어 주어진다.
셋째 줄에 목표 칸의 좌표 \(r_2\), \(c_2\)이 공백으로 구분되어 주어진다.
나이트가 시작 칸에서 목표 칸까지 이동하는 최소 횟수를 한 줄에 출력한다.
8
0 0
7 7
6
\(8 \times 8\) 표준 체스판에서 \((0,0)\)에서 \((7,7)\)까지는 \(6\)번 만에 이동할 수 있다.
5
2 2
2 2
0
시작 칸과 목표 칸이 같으므로 이동할 필요가 없어 답은 \(0\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
나이트의 최소 이동
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
나이트의 최소 이동