今天我参加了一场考试，遇到了一个算法问题。给定一个大小为N*M的国际象棋棋盘，我需要确定马从棋盘左下角到右上角所需最小步数。如何实现呢？
4个回答
2
一种使用 BFS 和 记忆化 的解决方案：
"NOVISITED" 可以取值为 "-1" 或 "null"，如果我们将可能的距离视为非负数 "[0，+inf)"。
每个方格的最小跳跃次数将在 "memo[row][column]" 中访问，因此从左下角到右上角的答案将在 "memo[N - 1][M - 1]" 处。
更新：
请注意，如果矩阵是方阵
# 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，则可以应用对称原则。- Alexander
1
1这是通过编程语言的最佳方式。+1 - BlackVegetable
1
我相信你可以将这个问题简化为三种情况：
你有一个没有解决方案的棋盘，例如：2w * 4h
你有一个解决方案为1的棋盘：2w * 3h
你有一个正方形的棋盘，因此有一个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步就到终点了。
通过编程语言，最好的解决方法是从当前位置开始映射所有可能的移动，并查看它们是否与终点匹配。如果不匹配，请检查您的问题是否现在变成了一个更简单的问题，您以前已经解决过。正如评论者所指出的那样，这可以通过记忆化来实现。
然而，如果您手动操作，我敢打赌您可以将其分解为少量的情况，就像我已经开始做的那样。
- BlackVegetable
5
“4 x 8” 可以在 4 步内解决。 - Alexander
可能需要修改一些东西吗？嗯，不对劲。 - BlackVegetable
是的，
4，打错了。你的意思是它没有解决方案，我错了吗？ - Alexander不，正如你指出的那样，我的模型并不完美。因为你可以移动到之前超出限制的区域之外，所以你不能完全限制棋盘。也许通过在每个方向上额外添加一行/列，你可以解决这个问题。你只能超出紧密的领域一个空间，否则就会变得愚蠢，离开你的目标。 - BlackVegetable
1可以证明，一个行数大于等于5，列数大于等于5的棋盘总是有解的。 - Rontogiannis Aristofanis
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
- Rontogiannis Aristofanis
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次跳跃才能到达目标位置。
（我让您自己想出所有适当的不等式和模数。）
- btilly
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接