卡在最小骑士的移动中以达到末端位置
我正在解决这个问题：
找到骑士从NXN国际象棋板中从开始位置移动到末端位置所需的最小步骤数。如果路径不存在，则返回-1
我写了以下代码：
def is_position_safe(n, cur_row, cur_col):
if 0 <= cur_row < n and 0 <= cur_col < n:
return True
else:
return False
def min_moves(n, cur_row, cur_col, end_row, end_col, visited):
if cur_row == end_row and cur_col == end_col:
return 0
key = tuple([cur_row, cur_col])
visited_temp = visited.copy()
if is_position_safe(n, cur_row, cur_col) and key not in visited:
visited_temp.append(key)
d1 = min_moves(n, cur_row - 2, cur_col - 1, end_row, end_col, visited_temp)
d2 = min_moves(n, cur_row - 2, cur_col + 1, end_row, end_col, visited_temp)
d3 = min_moves(n, cur_row - 1, cur_col - 2, end_row, end_col, visited_temp)
d4 = min_moves(n, cur_row - 1, cur_col + 2, end_row, end_col, visited_temp)
d5 = min_moves(n, cur_row + 1, cur_col - 2, end_row, end_col, visited_temp)
d6 = min_moves(n, cur_row + 1, cur_col + 2, end_row, end_col, visited_temp)
d7 = min_moves(n, cur_row + 2, cur_col - 1, end_row, end_col, visited_temp)
d8 = min_moves(n, cur_row + 2, cur_col + 1, end_row, end_col, visited_temp)
return min(d1, d2, d3, d4, d5, d6, d6, d7, d8) + 1
else:
return float('inf')
def min_knight_moves(n, cur_row, cur_col, end_row, end_col):
result = min_moves(n, cur_row, cur_col, end_row, end_col, [])
if result != float('inf'):
return result
else:
return -1
print(min_knight_moves(10, 9, 9, 6, 3))
在某些情况下它不起作用。例如，对于上述一个，它将返回我5，但实际答案是3。
我无法理解我在哪里做错了。有人可以帮我吗？
PS：我知道使用BFS有现有的解决方案，但是我正在尝试递归中的这个问题。我不太确定，我在哪里错了。感谢您的帮助。谢谢！
I am solving this question:
Find the minimum number of steps required by the knight to move from the starting position to the end position in a nXn chess board. If the path does not exists, then return -1
I have written the below code:
def is_position_safe(n, cur_row, cur_col):
if 0 <= cur_row < n and 0 <= cur_col < n:
return True
else:
return False
def min_moves(n, cur_row, cur_col, end_row, end_col, visited):
if cur_row == end_row and cur_col == end_col:
return 0
key = tuple([cur_row, cur_col])
visited_temp = visited.copy()
if is_position_safe(n, cur_row, cur_col) and key not in visited:
visited_temp.append(key)
d1 = min_moves(n, cur_row - 2, cur_col - 1, end_row, end_col, visited_temp)
d2 = min_moves(n, cur_row - 2, cur_col + 1, end_row, end_col, visited_temp)
d3 = min_moves(n, cur_row - 1, cur_col - 2, end_row, end_col, visited_temp)
d4 = min_moves(n, cur_row - 1, cur_col + 2, end_row, end_col, visited_temp)
d5 = min_moves(n, cur_row + 1, cur_col - 2, end_row, end_col, visited_temp)
d6 = min_moves(n, cur_row + 1, cur_col + 2, end_row, end_col, visited_temp)
d7 = min_moves(n, cur_row + 2, cur_col - 1, end_row, end_col, visited_temp)
d8 = min_moves(n, cur_row + 2, cur_col + 1, end_row, end_col, visited_temp)
return min(d1, d2, d3, d4, d5, d6, d6, d7, d8) + 1
else:
return float('inf')
def min_knight_moves(n, cur_row, cur_col, end_row, end_col):
result = min_moves(n, cur_row, cur_col, end_row, end_col, [])
if result != float('inf'):
return result
else:
return -1
print(min_knight_moves(10, 9, 9, 6, 3))
It is not working in some cases. Example, for the above one it is returning me 5, but the actual answer is 3.
I am not able to understand where I am doing wrong. Could anybody please help me.
P.S.: I know there are existing solutions out there, by using BFS, but I was trying this problem with recursion. I am not quite sure, where I am wrong. Appreciate your help. Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
回忆可能不是最好的情况，因为骑士可以从不同的路径到达某个位置，对于每条路径，都有不同的访问集。因此，我建议创建一个
visited_temp = visited.copy.copy（）并将其转发到递归中，而无需进行记忆。这个问题也称为自我避免步行问题。我已经发布了一个DFS解决方案，而没有记住的情况下，请避免步行在这里，但我选择了DFS，因为所有可能的路径都是目标。自从我说的那样，自避免步行就无法进行回忆，每条路径都有自己的访问。
请注意，由于您想要通过递归而不是BFS使用DFS，因此您的运行时间将成倍增长，因为您必须在决定之前计算所有路径。我选择了BFS方法，您可以阻止您到达目的地，因为BFS的性质。
由于运行时的指数爆炸，因此在10x10网格上运行建议的解决方案
需要很长时间，因此，对于以下类似的示例，我们得到的是：
对于6个或更多的网格，我杀死了运行，然后才结束。在这个问题上花费这么长时间的递归不是这样做的好方法
Memoization might not be the best case since a knight can reach a certain spot from different paths and for each path there is a different visited set. Therefore I would suggest creating a
visited_temp = visited.copy()and forward that into the recursion without uaing the memoization.This problem is also known as the self avoiding walk problem. I have posted a DFS solution without memoization to the self avoiding walk here but I chose DFS only since all the possible paths were the objective. Self avoiding walk can not have memoization since, as I said, each path has it's own visited set.
Note that since you want with DFS by recursion instead of BFS, your runtime will grow exponentially since you will have to compute all paths before deciding. I you chose the BFS approach you could stop one you reached the destination due tovthe nature of the BFS.
Running the suggested solution
on a 10X10 grid takes a very long time due to the exponential blowup in the runtime so for the following similar example on a lower grid we get:
For a grid size 6 or more I killed the run before it ended since it takes so long, recursion in this problem is not a good method for doing this