Cho bàn cờ n x n và quân mã đặc biệt di chuyển theo hình L: (x±a, y±b) hoặc (x±b, y±a). Tìm số nước đi tối thiểu từ (0,0) đến (n-1, n-1) cho mọi cặp (a,b) với 1 ≤ a,b < n. Kết quả -1 nếu không đạt được.
Thuật toán
Dùng BFS từ (0,0) với 8 hướng di chuyển tùy thuộc vào (a,b).
Lưu predecessor để truy vết đường đi khi đến đích.
Đối xứng: kết quả (a,b) = (b,a). Tối ưu: nếu (n-1) chia hết cho a thì (a,a) = (n-1)/a.
Mã nguồn 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)
Đầu ra (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