BFS 算法 - 具有约束步数的网格上最短行走
问题如下:一个流浪者从网格坐标(x,y)开始,想要到达坐标(0,0)。从每个网格点开始,漫游者可以向北走 8 步或向南 3 步或向东 5 步或向西 6 步(8N/3S/5E/6W)。
如何使用广度优先搜索找到从 (X,Y) 到 (0,0) 的最短路径?
说明:
- 无限网格
- 允许负坐标
- 必须使用队列(链表或数组)
- 不存在任何障碍
The problem is as follows: A wanderer begins on the grid coordinates (x,y) and wants to reach the coordinates (0,0). From every gridpoint, the wanderer can go 8 steps north OR 3 steps south OR 5 steps east OR 6 steps west (8N/3S/5E/6W).
How can I find the shortest route from (X,Y) to (0,0) using breadth-first search?
Clarifications:
- Unlimited grid
- Negative coordinates are allowed
- A queue (linked list or array) must be used
- No obstacles present
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
这个问题的算法是:
对于每个轴,朝它迈进,直到你在另一个轴上的位置为 0。
伪代码:
但是,我不明白为什么你需要搜索路线 - 这并不复杂。
The algorithm for this problem would be:
For each axis, step towards it until your position on the other axis is 0.
Pseudocode:
However, I don't understand why you need to search for a route - it's not that complicated.
正如“thejh”所说,不需要进行搜索,但您的作业需要进行搜索。
一个合理的方法是
分析。任意(x,y)起始位置都可能吗?检查允许的移动,您会发现它们可以组合起来产生 1 步水平移动和 1 步垂直移动,所以答案是肯定的(在您的提交中提供详细信息)。
弄清楚什么是“广度优先搜索”。维基百科是你的朋友(不过,如果你可以访问大学图书馆,我真的推荐帕特里克·亨利·温斯顿的旧人工智能,它真的很好,非常清晰的解释)。尝试解决一些更简单的问题。
以几乎相同的方式解决作业问题。如果您遇到任何 C++ 技术问题,请在此处询问。
干杯&呵呵,
As "thejh" remarked there's no need for a search, but your assignment calls for one.
A reasonable approach is
Analyze. Is it all possible for arbitrary (x, y) starting position? Checking the allowed moves you see that they can be combined to yield 1-step horizontal moves, and 1-step vertical moves, so the answer to that is yes (for your hand-in provide the details of this).
Figure out what "breadth-first search" is. Wikipedia is your friend (although, if you have access to a university library, I really do recommend Patrick Henry Winston's old Artifical Intelligence, it's really good, very lucid explanations). Try it out with some simpler problem.
Do the assignment's problem in just about the same way. Ask here if you encounter any technical C++ problem.
Cheers & hth.,
这是我使用队列的答案(实际上是基于 thejh 的答案):
它很复杂,但遵循指示。
Here's my answer (really based off of thejh's answer) that uses a queue:
It's convoluted, but follows the directions.
我将继续回答我自己的问题以供将来参考。
伪代码:
还应该注意的是,该应用程序的执行时间增长得非常非常快,因此请使用较小的坐标值对其进行测试。例如,坐标 (1,1) 给出 7 个级别的宽度,需要 16384 次迭代。
I'm going to go ahead and answer my own question for future reference.
Psuedocode:
It should also be noted that the execution time for this application grows very, very fast, so test it out with small coordinate values. For example, the coordinates (1,1) gives 7 levels of breadth and requires 16384 iterations.