向棋盘边缘移动的次数减少

Question

今天在一次考试中，我遇到了一道算法题，我得到了一个棋盘的大小N*M，我应该确定一个骑士从棋盘的左下角到右上角的最小可能移动次数是多少。如何做到这一点？

Answer 1

一个使用BFS和memoization的解决方案

# 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))

如果我们将可能的距离考虑为非负数[0,+inf)，则[0,+inf)可以具有值-1或null。

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

更新

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

Answer 2

我相信你可以将其简化为三种情况：

1. 您有一个没有解决方案的电路板示例: 2w *4h
2. 您有一个电路板的解决方案为1: 2w *3h
3. 您有一个正方形的电路板，因此解决方案为4: 3w * 3h

如果您有一个大于这些的板，您可以通过将一次移动的终点设置为更大板的起始点来将其减少到其中之一。

示例: 4w *5h大小的电路板：

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

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

从那里，把它简化成一个正方形的板子：

_ 1 e
3 _ _
s _ 2

它需要4个动作才能到达终点。因此，对于这种大小，您有1+4个移动=5。

我希望这足以让你入门。

编辑:这看起来并不完美。但是，它演示了一种解决此问题的启发式方法。这是另一个让你享受观看乐趣的案例：

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

在一块4x8的棋盘上有4个动作直到最后。

通过编程语言，通过从当前位置映射所有可能的移动并查看它们是否与终点匹配，可能会更好地解决这一问题。如果没有，请检查您的问题是否比以前解决的问题更简单。正如一位评论者指出的那样，这是通过memoization完成的。

但是，如果你是手工操作的，我打赌你可以像我开始做的那样，通过将它隔离在少量的案例中来解决它。

Answer 3

您可以使用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