用 Python 编写程序,找出棋子到达每个位置所需的最少移动次数

pythonserver side programmingprogramming更新于 2025/10/4 1:48:17

假设我们有一个棋盘和一个特殊的骑士棋子 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

相关文章


有用资源