Псевдокод для итеративного алгоритма dfs
Mark all unblocked positions in the maze as "UNVISITED"
push the start position's coordinates on the stack
mark the start position as “VISITED”
While (stack is not empty and end has not been found)
if the coordinate at the Top of the Stack is the end position
then end has been found (break out of loop)
if the coordinate at the Top of the Stack has an unvisited (and unblocked)
neighbor
push the coordinates of one unvisited neighbor on the stack
mark that one unvisited neighbor as visited
else
pop the coordinate at the Top of the Stack
If the stack is empty
The maze has no solution
else
The items on the stack contain the coordinates of the solution from the end
of the maze to the start of the maze.
C-код для итеративного алгоритма dfs, который возвращает лабиринт по значению и стек по ссылке
maze DEPTH_FIRST_SEARCH(Stack *s, maze m1)
{
int found = 0;
//Mark all unblocked positions in the maze as "UNVISITED
//push the start position's coordinates on the stack
int visited[m1.xsize+2][m1.ysize+2];
for(int i = 0; i < m1.xsize+2;i++)
{
for (int j = 0; j < m1.ysize+2; j++){
visited[i][j] = 0;
}
}
printf("Start: x: %d y:%d", m1.xstart,m1.ystart );
push(&s, m1.xstart,m1.ystart);
//mark the start position as “VISITED”
visited[m1.xstart][m1.ystart] = 1;
//While (stack is not empty and end has not been found)
while(found != 1)
{
struct Node* node = top(&s);
printf("x: %d y:%d", node->xcoord,node->ycoord );
//if the coordinate at the Top of the Stack is the end position
if((node->xcoord == m1.xend) && (node->ycoord == m1.yend))
{
//then end has been found (break out of loop)
found = 1;
break;
}
//if the coordinate at the Top of the Stack has an unvisited (and unblocked) down neighbor
else if(visited[(node->xcoord)-1][node->ycoord] = 0 && m1.arr[(node->xcoord)-1][node->ycoord] == '.')
{
//push the coordinates of one unvisited neighbor on the stack
//mark that one unvisited neighbor as visited
printf("down" );
push(&s,(((node->xcoord)-1)), node->ycoord );
visited[(node->xcoord)-1][node->ycoord] = 1;
}
//if the coordinate at the Top of the Stack has an unvisited (and unblocked) up neighbor
else if(visited[(node->xcoord)+1][node->ycoord] = 0 && m1.arr[(node->xcoord)+1][node->ycoord] == '.' )
{
//push the coordinates of one unvisited neighbor on the stack
//mark that one unvisited neighbor as visited
printf("up" );
push(&s,((node->xcoord)+1), node->ycoord);
visited[(node->xcoord)+1][node->ycoord] = 1;
}
//if the coordinate at the Top of the Stack has an unvisited (and unblocked) right neighbor
else if(visited[(node->xcoord)][node->ycoord+1] = 0 && m1.arr[(node->xcoord)][node->ycoord+1] == '.')
{
//push the coordinates of one unvisited neighbor on the stack
//mark that one unvisited neighbor as visited
printf("Right" );
push(&s,node->xcoord, ((node->ycoord)+1 ));
visited[(node->xcoord)][node->ycoord+1] = 1;
}
//if the coordinate at the Top of the Stack has an unvisited (and unblocked) left neighbor
else if(visited[(node->xcoord)][node->ycoord-1] = 0 && m1.arr[(node->xcoord)-1][node->ycoord-1] == '.')
{
//push the coordinates of one unvisited neighbor on the stack
//mark that one unvisited neighbor as visited
printf("left" );
push(&s,node->xcoord, ((node->ycoord)-1) );
visited[(node->xcoord)][node->ycoord-1] = 1;
}
else if(is_empty(s)==1)
{
break;
}
else
{
pop(&s);
}
}
return m1;
}
внутри main
int main (int argc, char **argv)
{
maze m1;
Stack *s;
//commandline arg checker
//debug checker
//take in file mazedata
//print out maze m1
m1 = DEPTH_FIRST_SEARCH(&s, m1);
//print out maze m1 after the dfs
}
Входные данные ./a.out mazedata1.txt Выходные данные
size: 10, 20
start: 1, 1
end: 10, 20
**********************
*s........*..........*
*........*...........*
*..*....*............*
*.*....*.............*
**....*..............*
*....*...............*
*...*................*
*..*.................*
*....................*
*...................e*
**********************
Я искал итеративные алгоритмы dfs для решения онлайн-лабиринтов, но я не мог найти в нем ничего, только рекурсивные алгоритмы dfs для решения графов и деревьев,Мой вывод только распечатывает лабиринт перед функцией dfs, а затем перестает работать в функции dfs и не печатает лабиринт после функции.Я не знаю, нужно ли мне включать функции стека и структуры узлов.Спасибо за помощь.