获取点到点的有效道路（矩阵上的 BFS）
Get effective road from a point to a point (BFS on matrix)
我有一个包含 0 和 X 的矩阵（0 表示您可以穿过，X 表示墙壁）。
我有一个起点和一个终点。
我使用 BFS 来找到起点和终点之间的最短路径（长度）。 （有用）
但现在我需要找到有效的道路，但我不知道该怎么做。 （我以为我可以使用 Lee 算法递归）。
Example:
5 5
SXXXF
0XX00
0XX0X
0000X
XXXXX
长度为8，道路为：(1, 1) -> (2, 1) -> (3, 1) ->(4, 2) -> (4, 3) -> (3 , 4) -> (2, 4) -> (1, 5)。
我有8个方向。
所以，我用BFS得到了长度（8），但我不知道如何得到路。
一些想法或伪代码？
谢谢！
其实很简单：
存储每个节点的"predecessor"。无论是在另一个矩阵中，嵌入到原始地图中，还是作为 Map。如果是双向的，即使是树结构也可以。
没有代码，我无法向您展示可能的解决方案，但最后，您只需要一个映射 node -> node from which it was visited。例如。在您的示例中，您从 (1, 1) 移动到 (2, 1)，因此映射将为 (2, 1)->(1, 1)。这可以很容易地在 BFS 例程中实现。
完成 运行 算法，同时填充映射。之后，您开始搜索结束节点的前导，然后搜索结束节点前导的前导，依此类推，直到您回到起点。
我有一个包含 0 和 X 的矩阵（0 表示您可以穿过，X 表示墙壁）。 我有一个起点和一个终点。 我使用 BFS 来找到起点和终点之间的最短路径（长度）。 （有用） 但现在我需要找到有效的道路，但我不知道该怎么做。 （我以为我可以使用 Lee 算法递归）。
Example:
5 5
SXXXF
0XX00
0XX0X
0000X
XXXXX
长度为8，道路为：(1, 1) -> (2, 1) -> (3, 1) ->(4, 2) -> (4, 3) -> (3 , 4) -> (2, 4) -> (1, 5)。 我有8个方向。
所以，我用BFS得到了长度（8），但我不知道如何得到路。 一些想法或伪代码？ 谢谢！
其实很简单：
存储每个节点的"predecessor"。无论是在另一个矩阵中，嵌入到原始地图中，还是作为 Map。如果是双向的，即使是树结构也可以。
没有代码，我无法向您展示可能的解决方案，但最后，您只需要一个映射 node -> node from which it was visited。例如。在您的示例中，您从 (1, 1) 移动到 (2, 1)，因此映射将为 (2, 1)->(1, 1)。这可以很容易地在 BFS 例程中实现。
完成 运行 算法，同时填充映射。之后，您开始搜索结束节点的前导，然后搜索结束节点前导的前导，依此类推，直到您回到起点。