Запись решения пути лабиринта с помощью стека

Я должен каким-то образом сгенерировать решение для лабиринта, используя реализацию стека из связанного списка. Лабиринт считывается из файла .txt и состоит из 0 для открытых пространств и 1 для стен. введите здесь описание изображения‹- Уверены, что выход должен быть в нижней строке? Итак, эти три 0?

Алгоритм, который я пытаюсь использовать, следующий:

While Not At End
    If Can Go North
        Go North
    ElseIf Can Go East
        Go East
    ElseIf Can Go South
        Go South
    ElseIf Can Go West 
        Go West
    EndIf
Wend

То, как я пытался это сделать, основывалось на операциях ++, выполняемых в индексе массива. Я не знал, что оператор индекса массива [ имеет приоритет над ++, поэтому теперь мне нужно переосмыслить обходной путь. Прежде чем сделать это, я хочу убедиться, что этот метод вообще будет работать. Может ли кто-нибудь взглянуть на мой код алгоритма и дать обратную связь? (Примечание: мне все еще нужно добавить некоторый код для отслеживания пройденных путей, чтобы избежать некоторого типа бесконечного цикла)

bool notSolved = true;
        int path = 0;
        row = 0;
        col = 0;

        rowStack.push(row);
        colStack.push(col);

        while (notSolved){

        //(from perspective of person looking at maze on screen)
        if (maze[row--][col] == 0){//if you can go up, go up
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row][col++] == 0){//else if you can go right, go right
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row++][col] == 0){//else if you can go down, go down
        rowStack.push(row);
        colStack.push(col);
        path++;
        }
        else if (maze[row][col--] == 0){//else if you can go left, go left
        rowStack.push(row);
        colStack.push(col);
        path++;
        }

            if((maze[row][col] == 0) && (row == (size - 1))){//if we reached an exit
                cout << "Solution Path:" << endl;
                for (int i = 0; i < path; i++){
                    cout << "row:" << rowStack.top() << " col:" << colStack.top() << endl;
                    rowStack.pop();
                    colStack.pop();
                }
            notSolved = false;
            }
        }

Проблема с выполнением [ перед ++: введите здесь описание изображения

Любая помощь приветствуется, спасибо!


c++ stack algorithm maze
person darko    schedule 30.11.2011    source источник
comment
рекурсия - ваш друг в этом.   -  person Erix    schedule 30.11.2011
comment
У вас есть конкретный вопрос?   -  person Jonathan M    schedule 30.11.2011
comment
Я не думаю, что этот алгоритм особенно хорош, например, если вы столкнетесь с правой стеной в горизонтальном туннеле, вы будете вечно прыгать туда-сюда справа налево.   -  person Seth Carnegie    schedule 30.11.2011
comment
@Erix Поиск в ширину лучше работает в лабиринтах, поэтому в этом случае очередь может быть лучшим «другом», чем рекурсия. Даже если вы решите пойти вглубь, вам может быть лучше использовать стек и цикл while вместо рекурсии. Поскольку пространство поиска растет как N^2, опасность переполнения стека при рекурсивном вызове становится вполне реальной.   -  person Sergey Kalinichenko    schedule 30.11.2011

Ответы (2)


arrow_upward
2
arrow_downward

Ваш алгоритм не будет работать в определенных лабиринтах с круговыми путями: как только вы попадете в один из них, вы будете двигаться по кругу. Чтобы исправить это, вам нужно добавить булев массив посещений[R][C][DIR], где DIR — это число от нуля до трех, представляющее направление. Когда вы покидаете ячейку [r][c] в направлении [d], задайте для Visit[r][c][d] значение true. В следующий раз, когда вы посетите ту же камеру, посмотрите, не покидали ли вы ее раньше в том же направлении; если вы это сделали, пропустите это направление и перейдите к следующему по цепочке.

person Sergey Kalinichenko    schedule 30.11.2011
comment
Хм, я думаю, что этот посещенный массив работает, но у меня проблемы. Есть ли лучший способ реализовать это в операторах if Вот проблема: imgur.com/5rstN, идет вправо, вниз, вправо, вправо, ударяется о стену, затем разворачивается и застревает. Вот мой новый код: pastebin.com/uhp9MKfc - person darko; 30.11.2011
comment
@mwmnj Код для проверки того, были ли вы на месте, выглядит хорошо, теперь вам нужно реализовать обратный поиск, причудливое название того, что делать, когда вы застряли. В вашем случае вам нужно вытолкнуть последний шаг из вашего rowStack/colStack, вернуться к предыдущей ячейке и продолжить в следующем направлении, которое вы раньше не пробовали. - person Sergey Kalinichenko; 30.11.2011
comment
хм, моя первоначальная мысль добавить еще в конце: else{//if stuck rowStack.pop(); colStack.pop(); row = rowStack.top(); col = colStack.top(); } Но теперь все, что, кажется, нужно сделать, это вытолкнуть каждый предыдущий шаг из вершины стека, пока он не станет пустым - person darko; 30.11.2011
comment
@mwmnj Вам нужно посмотреть наверх, прежде чем звонить в поп. Вам также необходимо проверить, пуст ли стек, прежде чем извлекать его. Наконец, вам нужно заключить ваши ifs в цикл, потому что, как только вы отступили, вам нужно продолжить движение в следующем направлении, которое вы еще не пробовали. - person Sergey Kalinichenko; 30.11.2011
comment
На что мне нужно обратить внимание, прежде чем звонить в поп? Что я пытаюсь сделать, так это заставить его вытолкнуть стеки, а затем переназначить строку и столбец на предыдущее значение пробелов, чтобы он пошел и попробовал любое направление, в котором он еще не пробовал. Мои операторы if заключены в цикл: Wnotsolved: pastebin.com/VSE2qBDu - person darko; 30.11.2011
comment
@mwmnj Вам нужно изменить порядок вызовов pop и top, например: else{ row = rowStack.top(); col = colStack.top(); rowStack.pop(); colStack.pop(); } - person Sergey Kalinichenko; 30.11.2011
comment
давайте продолжим это обсуждение в чате - person darko; 30.11.2011

arrow_upward
0
arrow_downward

++ и -- фактически изменяют переменные строки/столбца. Я думаю, вы хотите сделать maze[row - 1][col] == 0, а затем, как только вы переместитесь, обновить позицию в строке.

person Andy Ray    schedule 30.11.2011