使用广度优先搜索在迷宫中寻找最短路径
Using Breadth-First Search to find the shortest path in a maze
我有一个编码问题，我应该找到机器人在迷宫中从给定起点到终点的最短路径。输入格式如下：
输入第一行的两个数字（R，C），给出迷宫中的行数和列数，后面是 R 行输入，每行由 C 个字符组成。迷宫有一个标记为 S 的起点和一个标记为 E 的终点。井号 (#) 代表迷宫中的墙，点 (.) 代表迷宫中的自由方块。所以示例输入如下所示：
6 5
S....
.#...
..E..
.....
#....
#...#
机器人可以在所有四个方向上移动，所需的输出是写下机器人要遵循的方向，以最短路径从 S 到 E。我正在考虑使用标准的广度优先搜索。但是，有一种情况是，一旦机器人开始向一个方向移动，它就不能停下来，直到撞到墙 (#) 或到达迷宫的一端。使用标准的广度优先搜索可以让我找到最短路径，但它没有考虑到这种情况。你能建议如何修改算法才能工作吗？
谢谢。
如果您想最小化距离：
您所要做的就是向坐标添加一个额外的布尔值，说明方向是否垂直。当且仅当它撞到墙壁或迷宫的一端（使路径一分为二）时，布尔值才能更改。正是在这一刻，您必须将方向选择推送到与每条路径关联的堆栈上。
如果用布尔值存储已经遇到的节点，它将允许路径交叉但不会重复。使用广度优先算法，您会在第一次遇到终点时找到最短路径。路径关联的堆栈就是你搜索的结果。
如果您想减少订单数量
您必须更改您在算法中定义邻居的方式：对于所有四个方向，您都尝试尽可能地走远，并在达到极限时停止。每个方向的邻居是您到达的最后一个单元格。如果最后一个单元格已经被访问过，则它是无效的。
我有一个编码问题，我应该找到机器人在迷宫中从给定起点到终点的最短路径。输入格式如下： 输入第一行的两个数字（R，C），给出迷宫中的行数和列数，后面是 R 行输入，每行由 C 个字符组成。迷宫有一个标记为 S 的起点和一个标记为 E 的终点。井号 (#) 代表迷宫中的墙，点 (.) 代表迷宫中的自由方块。所以示例输入如下所示：
6 5
S....
.#...
..E..
.....
#....
#...#
机器人可以在所有四个方向上移动，所需的输出是写下机器人要遵循的方向，以最短路径从 S 到 E。我正在考虑使用标准的广度优先搜索。但是，有一种情况是，一旦机器人开始向一个方向移动，它就不能停下来，直到撞到墙 (#) 或到达迷宫的一端。使用标准的广度优先搜索可以让我找到最短路径，但它没有考虑到这种情况。你能建议如何修改算法才能工作吗？
谢谢。
如果您想最小化距离：
您所要做的就是向坐标添加一个额外的布尔值，说明方向是否垂直。当且仅当它撞到墙壁或迷宫的一端（使路径一分为二）时，布尔值才能更改。正是在这一刻，您必须将方向选择推送到与每条路径关联的堆栈上。
如果用布尔值存储已经遇到的节点，它将允许路径交叉但不会重复。使用广度优先算法，您会在第一次遇到终点时找到最短路径。路径关联的堆栈就是你搜索的结果。
如果您想减少订单数量
您必须更改您在算法中定义邻居的方式：对于所有四个方向，您都尝试尽可能地走远，并在达到极限时停止。每个方向的邻居是您到达的最后一个单元格。如果最后一个单元格已经被访问过，则它是无效的。