Итеративный алгоритм DFS дает ошибку Sigkill - PullRequest
0 голосов
/ 11 октября 2018

Псевдокод для итеративного алгоритма 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 и не печатает лабиринт после функции.Я не знаю, нужно ли мне включать функции стека и структуры узлов.Спасибо за помощь.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...