c++ - BFS 算法 - 具有约束步骤的网格上的最短步行

Question

问题如下:一个流浪者从网格坐标 (x,y) 开始，想到达坐标 (0,0)。从每个网格点开始，流浪者可以向北 8 步或向南 3 步或向东 5 步或向西 6 步 (8N/3S/5E/6W)。

如何使用广度优先搜索找到从 (X,Y) 到 (0,0) 的最短路线？

说明:

• 无限网格
• 允许负坐标
• 必须使用队列(链表或数组)
• 没有障碍物

Answer 1

这个问题的算法是:

对于每个轴，朝着它前进，直到您在另一个轴上的位置为 0。

伪代码:

while (x!=0) {
  if (x>0) x-=6;
  else x+=5;
}
while (y!=0) {
  if (y>0) y-=8;
  else y+=3;
}

但是，我不明白为什么您需要搜索路线 - 它并没有那么复杂。