数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 := 初始化为 -1 的新映射。
对于范围 1 到 n 的 i，执行以下操作：
对于范围 1 到 i 的 j，执行以下操作：
如果 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，执行以下操作：
打印 board[i, j]
打印 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
530 次查看
