用 Python 编写程序,找出棋子到达每个位置所需的最少移动次数
假设我们有一个棋盘和一个特殊的骑士棋子 K,它在棋盘内以 L 形移动。如果棋子在位置 (x1, y1) 并且移动到 (x2, y2),则移动可以描述为 x2 = x1 ± a ; y2 = y1 ± b 或 x2 = x1 ± b ; y2 = y1 ± a ; 其中 a 和 b 是整数。我们必须找出棋子从位置 (0, 0) 到达棋盘上的位置 (n-1, n-1) 所需的最少移动次数。如果某个位置无法到达,则将其标记为 -1,否则,返回移动次数。我们将打印 n – 1 行输出,每行 i 包含 n − 1 个整数,描述棋子必须为每个 j 进行的最少移动次数。
因此,如果输入为 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) 对初始化的新列表
ver := [(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 := element[0] + current_element[0]
y := element[1] + current_element[1]
如果-1 < x < n且-1 < y < n 且 temp_list[x, y] 与 (-1, -1) 相同,则
temp_list[x, y] := current_element
在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 := a new map initialized with -1
for i in range 1 to n, do
for j in range 1 to i, do
如果 board[i, j] 与 -1 相同,则
board[i, j] := path_search(i, j, n)
board[j, i] := board[i, j]
如果 (n - 1) mod i 与 0 相同,则
board[i, i] :=(n - 1) / i
对于范围从 1 到 n 的 i,执行
对于范围从 1 到 n - 1 的 j,执行
print(board[i, j])
print(board[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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

