체스판과 판 내에서 L자 모양으로 움직이는 특별한 기사 조각 K가 있다고 가정합니다. 조각이 (x1, y1) 위치에 있고 (x2, y2)로 이동하면 이동은 x2 =x1 ± a 로 설명될 수 있습니다. y2 =y1 ± b 또는 x2 =x1 ± b; y2 =y1 ± a; 여기서 및 b는 정수입니다. 우리는 그 체스 말이 위치 (0, 0)에서 체스 판의 위치 (n-1, n-1)에 도달하기 위해 도달하기 위한 최소 이동 수를 찾아야 합니다. 위치에 도달할 수 없으면 -1로 표시되고, 그렇지 않으면 이동 수가 반환됩니다. 우리는 n – 1줄의 출력을 인쇄할 것입니다. 여기서 각 줄 i에는 조각이 각 j에 대해 수행해야 하는 최소 이동 횟수를 설명하는 n – 1개의 정수가 포함됩니다.
따라서 입력이 n =6과 같으면 출력은 다음과 같습니다.
5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1
기사가 5x5 체스판의 위치(3, 3)에 있는 경우 가능한 이동입니다.
출력의 첫 번째 줄에는 조각이 (1,1)에서 (1,5) 위치에 도달하는 데 필요한 최소 이동 수가 포함됩니다. 연속된 라인은 유사하게 각각의 I 및 j 값에 대한 최소 이동 횟수를 나타냅니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
path_search() 함수를 정의합니다. i, j, n
이 걸립니다.-
temp_list :=쌍(-1, -1)으로 초기화된 새 지도
-
queue_positional :=쌍(0, 0)으로 초기화된 새 목록
-
버전 :=[(i, j) ,(-i, j) ,(i, -j) ,(-i, -j) ,(j, i) ,(j, -i) ,(-j, i ) ,(-j, -i) ]
-
queue_positional의 크기> 0인 동안 수행
-
current_element :=queue_positional에서 첫 번째 요소 삭제
-
ver의 각 요소에 대해 수행
-
x :=요소[0] + 현재_요소[0]
-
y :=요소[1] + 현재_요소[1]
-
-1
-
temp_list[x, y] :=현재 요소
-
queue_positional
끝에 쌍(x, y) 삽입 -
x가 n - 1과 같고 y가 n - 1과 같으면
-
count_var :=1
-
temp_list[x,y]가(0, 0)과 같지 않은 동안 수행
-
count_var :=count_var + 1
-
x, y :=temp_list[x,y]
-
-
count_var 반환
-
-
-
-
-
반환 -1
-
주요 기능/메서드에서 다음을 수행하십시오 -
-
board :=-1로 초기화된 새 지도
-
범위 1에서 n까지의 i에 대해 수행
-
범위 1에서 i까지의 j에 대해 수행
-
보드[i, j]가 -1과 같으면
-
보드[i, j] :=path_search(i, j, n)
-
보드[j, i] :=보드[i, j]
-
-
(n - 1) mod i가 0과 같으면
-
보드[i, i] :=(n - 1) / i
-
-
-
-
범위 1에서 n까지의 i에 대해 수행
-
범위 1에서 n - 1에 있는 j에 대해 수행
-
인쇄(보드[i,j])
-
-
인쇄(보드[i,n - 1])
-
소스 코드(Python)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import defaultdict def path_search(i, j, n): temp_list = defaultdict(lambda: (-1,-1)) queue_positional = [(0, 0)] ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)] while len(queue_positional) > 0: current_element = queue_positional.pop(0) for element in ver: x = element[0] + current_element[0] y = element[1] + current_element[1] if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1): temp_list[x, y] = current_element queue_positional.append((x, y)) if x == n - 1 and y == n - 1: count_var = 1 while temp_list[x,y]!=(0,0): count_var += 1 x, y = temp_list[x,y] return count_var return -1 def solve(n): board = defaultdict(lambda: -1) for i in range(1, n): for j in range(1, i): if board[i, j] == -1: board[i, j] = path_search(i, j, n) board[j, i] = board[i, j] if (n - 1) % i == 0: board[i, i] = (n - 1) / i for i in range(1, n): for j in range(1, n - 1): print(int(board[i, j]), end = ' ') print(int(board[i, n - 1])) solve(6)
입력
6
출력
5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1