减少棋盘边缘的移动

Question

今天在一次考试中，我得到了一道算法题，题中给出了棋盘的N*M大小，我应该确定骑士从棋盘的左下边缘到右上边缘所能做的最小移动次数。怎么能做到呢？

Answer 1

你可以使用BFS或DFS模拟骑士的移动。我个人更喜欢DFS方法，因为它可以递归实现。如果您有一个函数process，它将当前x位置、当前y位置、表格的行、表格的列和计数器作为参数，那么解决方案如下所示：

/* .......... */
process(x-1, y-2, R, C, count+1);
process(x+1, y-2, R, C, count+1);
process(x-2, y-1, R, C, count+1);
process(x-2, y+1, R, C, count+1);
process(x-1, y+2, R, C, count+1);
process(x+1, y+2, R, C, count+1);
process(x+2, y-1, R, C, count+1);
process(x+2, y+1, R, C, count+1);
/* .......... */

到达目的地后，返回当前的count值。

编辑：也可以使用动态规划来解决。你把dp（i，j）定义为到达正方形（i，j）的最佳方式。所以dp（i，j）等于：

dp(i,j) = min{dp(all squares that can reach (i,j) in one move)} + 1

Answer 2

我相信你可以把这减少到三种情况：

>

你有一个没有解决方案的板示例：2w*4h

你有一块1:2w*3h的电路板

你有一个正方形的电路板，因此有一个4:3w*3h的解决方案

如果您有一个比这些大的棋盘，您可以通过将一次移动的endpoint设置为更大棋盘的起点来将其缩小到其中之一。

示例：尺寸为4w*5h的板：

_ _ _ _
_ _ _ _
_ e _ _
_ _ _ _
s _ _ _

其中s是开始，e是结束。

从这里开始，将其缩小为方形板：

_ 1 e
3 _ _
s _ 2

需要4步才能到达终点。所以对于这个尺寸，你有1 4步=5步。

我希望这足以让你开始。

编辑：这似乎并不完美。然而，它展示了一种解决这个问题的启发式方法。下面是另一个让你享受观看乐趣的例子：

_ _ _ e
_ 3 _ _
_ _ _ _
_ _ 2 _
_ _ _ _
_ 1 _ _
_ _ _ _
s _ _ _

在4x8板上有4个动作直到结束。

通过编程lanugage，可以更好地解决这个问题，方法是首先从当前位置映射所有可能的移动，并查看它们是否匹配终点。如果他们没有，检查你的问题是否是你以前解决过的更简单的问题。正如一位评论人士所指出的那样，这是通过备忘录实现的。

然而，如果你用手做这件事，我敢打赌，你可以像我已经开始做的那样，通过将它隔离成少量的案例来解决它。

Answer 3

使用BFS和备忘录的解决方案：

# Memoization
memo = a matrix of NOVISITED of size N x M

# Starting position
# (row, column, jumps)
queue.push((0, 0, 0))

while queue is not empty:
  # Get next not visited position
  row, column, jumps = queue.pop()

  # Mark as visited
  memo[row][column] = jumps

  for each possible move (nrow, ncolumn) from (row, column):
    if memo[nrow][ncolumn] is NOVISITED:
      # Queue next possible move
      queue.append((nrow, ncolumn, jumps + 1))

NOVISITED可以有值-1或null，如果我们将可能的距离视为非负数[0， inf）。

在memo[row][column]中，每个方块的最小跳转次数将是可接受的，因此从左下角开始的右上角的答案将位于memo[N-1][M-1]。

更新

请注意，如果矩阵是正方形nxn，则可以应用对称原则。