使用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包含描述棋子必须进行的每个j的最小移动次数的n-1个整数。

因此，如果输入为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

如果骑士处于5×5的棋盘的位置（3,3），则它的可行移动范围如上图所示。

输出的第一行包含棋子到达位置（1,1）到（1,5）所需的最小移动次数。后续行类似地描述了其各自的i和j值的最小移动次数。

源代码（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)