3

今天在一次考试中，我得到了一个算法问题，我得到了一个棋盘的大小 N*M，我应该确定一个骑士从棋盘的左下角可以走的最小可能移动数是多少到右上边缘。怎么可能呢？

4

4 回答 4

2

使用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))

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

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

更新

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

于 2012-06-28T17:53:42.107 回答
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);
/* .......... */

当您到达目的地时，您返回计数的当前值。

编辑：它也可以使用动态编程来解决。您定义dp(i,j)为到达广场 (i,j) 的最佳方式。所以 dp(i,j) 等于：

dp(i,j) = min{dp(all squares that can reach (i,j) in one move)} + 1
于 2012-06-28T19:17:07.687 回答
1

我相信您可以将其减少到三种情况：

  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 个动作直到结束。

通过编程语言，可以通过从当前位置映射所有可能的移动并查看它们是否与终点匹配来更好地解决这个问题。如果他们不这样做，请检查您的问题现在是否是您以前解决过的更简单的问题。正如评论者指出的那样，这是通过记忆实现的。

但是，如果您是手动执行此操作，我敢打赌，您可以像我已经开始做的那样，通过将其隔离为少数情况来解决它。

于 2012-06-28T17:03:57.210 回答
1

这是有效的解决方案。

一是特殊情况。如果n = 1不能跳，问题只能解决(1, 1)。如果n = 2通过检查只有一条路可以走，而问题只有m = 4k + 3在这种情况下需要2k + 1跳跃才能到达那里时才能解决。如果 ，则相反m = 1,2。

现在一般情况。骑士有 8 次可能的跳跃，它朝一个方向跳 2 次，然后朝另一个方向跳 1 次。可能的方向是r, l, u, d（右、左、上、下）。因此，让它nru向右跳 2 次，然后向上跳 1 次，其他 7 次可能的跳跃也是如此。那么答案必须是以下方程组的解：

n - 1 = 2*nru + nur - nul - 2*nlu - 2*nld - ndl + ndr + 2*nrd
m - 1 = nru + 2*nur + 2*nul + nlu - nld - 2*ndl - 2*ndr - nrd

跳跃次数为：

nru + nur + nul + nlu + nld + ndl + ndr + nrd

我们希望跳跃的次数尽可能少。直观地说，如果我们有一组满足前两个等式的数字，并且我们已经将跳跃次数降低了，那么我们应该很容易找到将留在框内的跳跃的顺序。我不会证明这一点，但事实证明，如果2 < n和2 < m。

因此解决这个整数规划问题（解决这两个方程，使跳跃次数尽可能低），我们就有了答案。有解决此问题的方法，但这个特殊问题非常简单。我们只是做“显而易见的事情”来接近我们的目标，计算出几个额外的跳跃，不难证明这是整数方程的最优解，因此必须是国际象棋的答案问题。

那么显而易见的事情是什么？首先，如果m < n，我们可以将板翻转过来，所以不失一般性，我们可以假设n < m。（棋盘离你的距离至少和它离你的距离一样远。）鉴于这一事实，显而易见的事情是向左上跳，直到你撞到墙，或者你撞到从角落向下延伸的对角线。此时，您沿着墙壁或对角线向目标前进。

如果您直接降落在目标上，您将获得最佳答案。

如果你沿着墙走并错过了 1，事实证明，通过将你的一个跳跃转换成一对，你最终会到达你需要的地方。如果你沿着墙走，但错过了 2 次（即你是一个对角线），那么你需要插入 2 次跳跃。（距离表明你至少需要一个，一个简单的奇偶性参数表明你至少需要 2 个，一对跳跃就可以做到。）

如果你沿着对角线走并且错过了 1，插入一对跳跃，你很好。

如果你沿着对角线走并且错过了 2 次，那么将一对右上/右上转换为右上/右上/左上/左上，你只需再跳 2 次即可完成。

如果你没有沿着对角线移动，但有一个左上，将其转换为右上/左上/右上三联体，你只需再跳 2 次即可。

剩下的特殊情况是一个 3x3 板，需要 4 次跳跃。

（我把它留给你来找出所有合适的不等式和模数。）

于 2012-06-28T20:12:15.183 回答