Найти все пути в лабиринте, используя DFS
Учитывая источник и ячейку назначения в лабиринте, я хотел бы найти все возможные решения для лабиринта с использованием 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: ТАК в настоящее время не позволяет мне вставлять изображения, и поэтому он автоматически создал ссылку.
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;
}
2 ответа
Я думаю, что вам нужно очистить соответствующее поле в посещенных, где вы удалите точку из стека.
Изменить: Другая проблема заключается в том, что вам нужно вернуться, когда вы достигли цели. И в вашем стеке, вероятно, не очевидно, что такое неисследованные альтернативы и каков текущий путь (вы могли бы использовать посещенный массив для отслеживания этого, но это кажется более запутанным, чем "просто" с использованием рекурсии или добавления соответствующей информации в твой стек
Кроме того, последующие узлы должны быть отмечены как посещенные, когда они на самом деле исследуются, а не когда они помещаются в стек.
Некоторые замечания
Я думаю, что код будет более читабельным, используя рекурсию вместо явного стека
Вам на самом деле не нужно посещаться, вы можете просто временно изменить поля лабиринта на пути к 1 (вероятно, не сделайте этого в "реальном" коде, где лабиринт должен быть неизменным). В противном случае я бы просто структурировал его так же, как лабиринт.
Я бы изменил толчок, чтобы взять точку симметрии.
Избегайте избыточности вздутие живота кода. Например,
front == NULLфилиал вpushизбыточно с регистром по умолчанию - регистр по умолчанию будет делать то же самое в случае NULL.
Изменить 2:
Если вы действительно хотите избежать рекурсии, я бы изменил структуру данных так:
typedef struct PathElement {
int x;
int y;
int direction_to_next;
struct PathElement* next;
struct PathElement* prev;
} path;
Это позволит вам легко двигаться в любом направлении (например, вы будете в конце пути, когда захотите распечатать). Когда вы вернетесь к PathElement, увеличьте direction_to_next и продолжайте там, пока не исчерпаете все 4 возможных направления. Не выдвигайте альтернативы раньше времени.
Для каждой точки в вашем поиске сохраните ссылку на предыдущую точку. Всегда извлекайте предмет из стека после работы с ним. Обратите внимание, что если нет решения, ваш код будет бесконечный цикл. И когда вы дойдете до конца, вы можете использовать предшественников, чтобы вернуться и найти полный путь.
Избавьтесь от вашего посещенного массива и, чтобы предотвратить циклы во время DFS, убедитесь, что точка, которую вы добавляете к пути, в данный момент не находится в пути. Поскольку у вас есть только 30 возможных точек в вашем лабиринте, вы можете использовать битовое поле, чтобы указать, находится ли данная точка на пути.
Кроме того, не выходите из цикла преждевременно (при обнаружении первого доступного хода).