使用DFS查找迷宫中的所有路径 [英] Find all paths in a maze using DFS
问题描述
给出迷宫中的源单元格和目标单元格，我想找到使用DFS迷宫的所有可能的解决方案. 0代表我的迷宫中的一堵墙.
Given a source and a destination cell in a maze, I would like to find all possible solutions to a maze using DFS. 0 represents a wall in my maze.
我已经成功编写了一个程序，但这只给了我一个路径.我已经想到了将其扩展到所有路径的所有可能性，但可悲的是，即使经过数小时(准确地说是2天)，我仍然无法提出解决方案.
I've successfully written a program, but that gives me only one path. I've thought of all the possibilities to extend it to all paths but sadly even after being hours(2 days to be precise) at it, I was unable to come up with a solution.
我考虑为每个节点保留一个已访问"数组，以便在回溯时不会对上一个节点执行相同的动作.但是，这样做只会产生一条完全不同的路径(如果有的话)，并且没有相同的节点.
I thought of keeping a "visited" array for each node so that when I backtrack I don't perform the same move for the previous node. However doing that would only produce a path that is completely distinct(if there is any) with no nodes being the same.
我也想到了其他方法，但是即使那样也带来了一些问题.
I also thought of some other way but even that posed some problem.
我也检查了类似的问题，但是它们都不是我所特有的.有一个使用显式递归的解决方案.但是，我想要的是使用堆栈并找到所有可能的路径.可悲的是，我找不到任何可信的东西(至少以我能理解的方式).
I've also checked out similar questions but none of them are specific to my context. There is a solution using explicit recursion. However, what I want is to use a stack and find all possible paths. Sadly, I couldn't find anything credible(at least in a way that I could understand).
这是我一个路径的代码.
编辑:我现在已经实现了适当的" DFS.我还添加了一个堆栈来跟踪当前路径.然后，程序还将检查未探索的节点.但是，它以其他顺序检查，因此我仍然只能获得一条路径！
Edit: I've now implemented the "proper" DFS. I've also added a stack to keep track of the current path. The program then also checks for the unexplored nodes. However, its checking in some other order and therefore I still can get only one path!
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
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)
{
if(front==NULL)
{
front = (stack*)malloc(sizeof(stack));
front -> pt.x = x; front -> pt.y = y;
front -> next = NULL;
return;
}
stack* temp = (stack*)malloc(sizeof(stack));
temp -> pt.x = x; temp -> pt.y = y;
temp -> next = front;
front = temp;
}
Point pop()
{
if(front != NULL)
{
stack* temp = front;
Point pt = front -> pt;
front = front -> next;
free(temp);
return pt;
}
}
void push_path(int x, int y)
{
if(front_path==NULL)
{
front_path = (stack*)malloc(sizeof(stack_path));
front_path -> pt.x = x; front_path -> pt.y = y;
front_path -> next = NULL;
return;
}
stack_path* temp = (stack*)malloc(sizeof(stack_path));
temp -> pt.x = x; temp -> pt.y = y;
temp -> next = front_path;
front_path = temp;
}
Point pop_path()
{
if(front_path != NULL)
{
stack_path* temp = front_path;
Point pt = front_path -> pt;
front_path = front_path -> next;
free(temp);
return pt;
}
}
bool inMaze(Point pt)
{
return (pt.x>=0 && pt.y>=0 && pt.x<5 && pt.y<6);
}
int main()
{
struct Point pt1;
int visited[30]={0};
push(0,0);
push_path(0,0);
struct Point dest = {3,4};
int maze[5][6] = {{1,0,1,1,1,1},
{1,0,1,0,1,1},
{1,1,1,0,1,1},
{0,0,0,0,1,0},
{1,1,1,0,1,1}};
int paths[30]={0};
int dx[4]={-1, 0, 0, 1};
int dy[4]={0,-1, 1, 0};
while(front!=NULL)
{
Point pt = pop();
if(pt.x==dest.x && pt.y==dest.y)
{
push_path(pt.x,pt.y);
int i;
visited[6*pt.x+pt.y] = 0;
stack_path *temp = front_path;
while(temp!=NULL)
{
printf("%d%d ",temp->pt.x, temp->pt.y);
temp = temp->next;
}
printf("\n");
pop_path();
}
else
{
if(!visited[6*pt.x+pt.y])
{
visited[6*pt.x+pt.y] = 1;
push_path(pt.x,pt.y);
}
int i;
int flag =0;
for(i=0; i<4; i++)
{
pt1.x = dx[i] + pt.x;
pt1.y = dy[i] + pt.y;
if(inMaze(pt1) && maze[pt1.x][pt1.y]==1 && visited[6*pt1.x+ pt1.y]==0)
{
push(pt1.x,pt1.y);
flag = 1;
}
}
if(flag==0)
pop_path();
}
}
return 0;
}
有人可以指导我修改此代码，以便它找到所有路径.期待社区的帮助！
Can someone please guide me to modify this code such that it finds all paths. Expecting the community's help!
PS:因此，当前不允许我嵌入图像，因此它已自动创建了一个链接.
PS: SO currently doesn't allow me to embed images and therefore it has automatically created a link.
PS:该问题被标记为与其他问题重复.供您参考，在发布问题之前，我已经仔细考虑了该问题！如果有人在那里读过答案，您会发现它不是已接受" ！它只是说您需要进行全部" 排列！如果只有一个人愿意打扰另一个答案(在另一个问题中)，他们会意识到，它仅适用于向北，东北或东方向移动！而且，我也很清楚地表明我不想要一个递归解决方案-这就是另一个问题正在使用的方式！
PS: This question has been marked as duplicate relating to some other question. For your information, I had gone through that very question before posting my question! If anyone would have read the answer there, you could see it wasn't "accepted"! It just says you need to do "all" permutations! If only one would have bothered to go through the other answer(in the other question), they would have realised that it only applied to moving in north, northeast, or east directions! Moreover, I also had made it pretty clear that I don't want a recursive solution - that's what the other question was using!
有效的解决方案
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Point
{
int x,y;
}Point;
typedef struct stack
{
struct Point pt;
struct stack* next;
int dir_count;
}stack;
stack*front =NULL;
void push(int x, int y)
{
stack* temp = (stack*)malloc(sizeof(stack));
temp -> pt.x = x; temp -> pt.y = y;
temp -> next = front;
front = temp;
}
Point pop()
{
if(front != NULL)
{
stack* temp = front;
Point pt = front -> pt;
front = front -> next;
free(temp);
return pt;
}
}
bool inMaze(Point pt)
{
return (pt.x>=0 && pt.y>=0 && pt.x<5 && pt.y<6);
}
int main()
{
struct Point pt1,pt2;
struct Point pt = {0,0};
push(0,0);
front->dir_count = 0;
struct Point dest = {3,4};
int maze[5][6] = {{1,0,1,1,1,1},{1,0,1,0,1,1},{1,1,1,0,1,1},{0,0,0,0,1,0},{1,1,1,0,1,1}};
int dx[4]={-1, 0, 0, 1};
int dy[4]={0,-1, 1, 0};
int flag_pop = 0;
while(front != NULL)
{
if(front->pt.x==dest.x && front->pt.y==dest.y)
{
stack* temp = front;
while(temp != NULL)
{
printf("%d%d ", temp->pt.x, temp->pt.y);
temp = temp->next;
}
printf("\n");
pt = pop();
}
else
{
int i,k;
int flag_push =0, count = 0, moves=0;
for(k=0;k<4;k++)
{
pt2.x = dx[k] + front->pt.x;
pt2.y = dy[k] + front->pt.y;
if(maze[pt2.x][pt2.y]==0 || !inMaze(pt2) || !(pt.x != pt2.x || pt.y != pt2.y))
count++;
}
// count of possible moves for each node
moves = 4-count;
for(i=0; i<4; i++)
{
int flag=0;
pt1.x = dx[i] + front->pt.x;
pt1.y = dy[i] + front->pt.y;
// if moves are exhausted
if(!(front->dir_count<moves))
break;
if(inMaze(pt1) && maze[pt1.x][pt1.y]==1 && (pt.x != pt1.x || pt.y != pt1.y) )
{
stack* temp = front;
while(temp != NULL)
{
if(temp->pt.x == pt1.x && temp->pt.y == pt1.y)
{
flag = 1;
break;
}
temp = temp->next;
}
// if node is not there in the path
if(flag==0)
{
front->dir_count++;
push(pt1.x, pt1.y);
front -> dir_count = 0;
flag_push = 1;
break;
}
}
}
// if no move was done
if(flag_push==0)
{
pt = pop();
}
}
}
return 0;
}
推荐答案
我认为您需要清除已访问的相应字段，然后从堆栈中删除该点.
I think you need to clear the corresponding field in visited where you remove the point from the stack.
编辑:另一个问题是，达到目标后需要回溯.在您的堆栈上，可能尚不清楚什么是未开发的替代方案以及当前路径是什么(您可能能够使用Visited数组来对此进行跟踪，但与使用递归或将相应信息添加到其中的只是"相比，它似乎更令人费解.您的堆栈结构)
Edit: Another issue is that you need to backtrack when you have reached the goal. And on your stack, it's probably not obvious what unexplored alternatives are and what the current path is (you might be able to use the visited array to track this, but it seems more convoluted than "just" using recursion or adding the corresponding information to your Stack stuct)
此外，应在实际调查后续节点时将其标记为已访问，而不是在将其压入堆栈时标记为已访问.
Also, subsequent nodes should be marked visited when they are actually investigated, not when they are pushed on the stack.
一些评论
-
我认为使用递归而不是显式堆栈可以使代码更具可读性
I think the code would be more readable using recursion instead of an explicit stack
您实际上并不需要访问，您可以将路径上的迷宫字段临时更改为1(可能不会在真实"代码中执行此操作，但迷宫应该是不可变的).否则，我将以与迷宫相同的方式构造它.
You don't really need visited, you could just change maze fields on the path to 1 temporarily (probably wouldn't do this in "real" code where the maze should be immutable though). Otherwise, I'd just structure it the same way as the maze.
我会更改推力以获取对称点.
I'd change push to take a point for symmetry.
避免多余的代码使代码膨胀.例如，在默认情况下，push中的front == NULL分支是多余的-在NULL情况下，默认情况下会做完全相同的事情.
Avoid redundancies bloating the code. For instance, the front == NULL branch in push is redundant with the default case -- the default case will do exactly the same thing in the NULL case.
编辑2 :
如果您真的想避免递归，那么我将数据结构更改为:
If you really want to avoid recursion, I'd change the data structure to this:
typedef struct PathElement {
int x;
int y;
int direction_to_next;
struct PathElement* next;
struct PathElement* prev;
} path;
这将使您可以轻松地向任何方向移动(例如，要打印时，您将位于路径的尽头).当您回溯到PathElement时，增加direction_to_next并继续进行，直到用尽所有4个可能的方向.不要提前推"其他选择.
This will allow you to easily go in any direction (for instance, you'll be at the end of a path when you want to print). When you backtrack to a PathElement, increment direction_to_next and continue there until you have exhausted all 4 possible directions. Don't "push" alternatives ahead of time.
这篇关于使用DFS查找迷宫中的所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
