Giả sử, chúng ta có một bàn cờ và một quân cờ đặc biệt K, di chuyển theo hình chữ L trong bàn cờ. Nếu mảnh ở vị trí (x1, y1) và nếu nó di chuyển đến (x2, y2) thì chuyển động có thể được mô tả là x2 =x1 ± a; y2 =y1 ± b hoặc x2 =x1 ± b; y2 =y1 ± a; trong đó a và b là các số nguyên. Ta phải tìm ra số nước đi tối thiểu của quân cờ đó để đạt được vị trí (n-1, n-1) trên bàn cờ từ vị trí (0, 0). Nếu một vị trí không thể truy cập được, nó được đánh dấu -1, ngược lại, số lần di chuyển được trả về. Chúng tôi sẽ in ra n - 1 dòng đầu ra, trong đó trong mỗi dòng i, nó sẽ chứa n - 1 số nguyên mô tả số lần di chuyển tối thiểu mà quân cờ phải thực hiện cho mỗi j.
Vì vậy, nếu đầu vào là n =6, thì đầu ra sẽ là
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
Các nước đi có thể có cho quân sĩ nếu nó ở vị trí (3, 3) trong bàn cờ 5x5.
Dòng đầu tiên của đầu ra chứa số lần di chuyển tối thiểu của quân cờ để đạt được vị trí (1,1) đến (1,5). Các dòng liên tiếp mô tả tương tự số lần di chuyển tối thiểu cho mỗi giá trị I và j tương ứng.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm path_search (). Điều này sẽ mất i, j, n
-
temp_list:=một bản đồ mới được khởi tạo với các cặp (-1, -1)
-
queue_positional:=một danh sách mới được khởi tạo bởi các cặp (0, 0)
-
ver:=[(i, j), (- i, j), (i, -j), (- i, -j), (j, i), (j, -i), (- j, i ), (- j, -i)]
-
trong khi kích thước queue_positional> 0, thực hiện
-
current_element:=xóa phần tử đầu tiên khỏi queue_positional
-
cho mỗi phần tử trong ver, do
-
x:=element [0] + current_element [0]
-
y:=element [1] + current_element [1]
-
nếu -1
-
temp_list [x, y]:=current_element
-
chèn cặp (x, y) vào cuối queue_positional
-
nếu x giống với n - 1 và y giống với n - 1 thì
-
count_var:=1
-
trong khi temp_list [x, y] không giống với (0, 0), hãy làm
-
count_var:=count_var + 1
-
x, y:=temp_list [x, y]
-
-
return count_var
-
-
-
-
-
trả về -1
-
Từ hàm / phương thức chính, hãy thực hiện như sau -
-
board:=một bản đồ mới được khởi tạo với -1
-
đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện
-
đối với j trong phạm vi 1 đến i, thực hiện
-
nếu bảng [i, j] giống -1, thì
-
board [i, j]:=path_search (i, j, n)
-
board [j, i]:=board [i, j]
-
-
nếu (n - 1) mod i giống 0, thì
-
bảng [i, i]:=(n - 1) / i
-
-
-
-
đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện
-
đối với j trong phạm vi từ 1 đến n - 1, thực hiện
-
print (board [i, j])
-
-
print (board [i, n - 1])
-
Mã nguồn (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)
Đầu vào
6
Đầu ra
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