Tag: 迷宫

使用DFS查找迷宫中的所有路径

给定迷宫中的源和目标单元格，我想使用DFS找到迷宫的所有可能解决方案。 0表示我迷宫中的墙。 可视化迷宫 我已经成功编写了一个程序，但这只给了我一条路。 我已经想到了将它扩展到所有路径的所有可能性，但遗憾的是，即使经过数小时（确切地说是2天），我也无法找到解决方案。 我想为每个节点保留一个“访问过的”数组，这样当我回溯时，我不会对前一个节点执行相同的移动。 但是，这样做只会产生一个完全不同的路径（如果有的话），没有相同的节点。 我还想到了一些其他的方式，但即使这也提出了一些问题。 我也检查了类似的问题，但没有一个是针对我的背景。 有一个使用显式递归的解决方案。 但是，我想要的是使用堆栈并找到所有可能的路径。 可悲的是，我找不到任何可信的东西（至少以我能理解的方式）。 这是我的一条路径的代码。 编辑 ：我现在已经实现了“正确的”DFS。 我还添加了一个堆栈来跟踪当前路径。 然后程序还会检查未探测的节点。 但是，它检查其他一些顺序，因此我仍然只能获得一条路径！ #include #include #include typedef struct Point { int x,y; }Point; typedef struct stack { struct Point pt; struct stack* next; void push(int, int); Point pop(); }stack, stack_path; stack*front =NULL; stack_path*front_path =NULL; void push(int x, int y) { […]

如何在迷宫中找到最快的路线（在C中）

迷宫被定义为方阵。 例如： int maze[N][N] = { { 1, 1, 1, 1, 1, 1, 1 }, { 0, 1, 0, 1, 0, 0, 1 }, { 0, 1, 0, 1, 1, 1, 1 }, { 0, 1, 0, 0, 0, 1, 1 }, { 0, 1, 1, 1, 0, 1, 1 }, { 0, 0, 1, […]