<分区>
给定迷宫中的源单元格和目标单元格，我想使用 DFS 找到迷宫的所有可能解决方案。 0 代表我迷宫中的一堵墙。
我已经成功编写了一个程序，但这只给了我一个路径。我已经考虑过将它扩展到所有路径的所有可能性，但遗憾的是，即使在数小时(准确地说是 2 天)之后，我也无法提出解决方案。
我想为每个 节点保留一个“已访问”数组，这样当我回溯时，我就不会对前一个节点执行相同的移动。然而，这样做只会产生一条完全不同的路径(如果有的话)，没有相同的节点。
我也想到了一些其他的方法，但即使这样也带来了一些问题。
我也检查过类似的问题，但它们都不是特定我的上下文。有一个使用显式递归的解决方案。但是，我想要的是使用堆栈并找到所有可能的路径。可悲的是，我找不到任何可信的东西(至少以我能理解的方式)。
这是我的一个路径的代码。
编辑:我现在已经实现了“适当的”DFS。我还添加了一个堆栈来跟踪当前路径。该程序然后还检查未探索的节点。但是，它以其他顺序检查，因此我仍然只能获得一条路径!
#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;
}
有人可以指导我修改这段代码，使其找到所有路径。期待社区的帮助!
PS:SO 目前不允许我嵌入图片，因此它自动创建了一个链接。
PS:此问题已被标记为与其他一些问题相关的重复问题。为了您的信息，我在发布问题之前已经解决了这个问题!如果有人会在那里阅读答案，您会发现它不是“已接受”!它只是说您需要进行“所有” 排列!如果只有一个人愿意仔细阅读另一个答案(在另一个问题中)，他们就会意识到它仅适用于向北、东北或东方向移动!此外，我还明确表示我不想要一个递归解决方案——这就是另一个问题所使用的!
编辑 2: 工作解决方案
#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;
}