Запись решения лабиринта с помощью стека - PullRequest
Новая
       34

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

1 голос
/ 30 ноября 2011

Я должен создать решение для лабиринта, используя реализацию стека связным списком каким-то образом. Лабиринт читается из файла .txt и состоит из 0 для открытых пространств и 1 для стен. enter image description here <- Уверен, выход должен быть в нижнем ряду? Так эти три 0? </p>

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

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;
            }
        }

Проблема с выполнением [before ++: enter image description here

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

Ответы [ 2 ]

2 голосов
/ 30 ноября 2011

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

0 голосов
/ 30 ноября 2011

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

...