c++ - 用堆栈记录迷宫路径解决方案

Question

我要以某种方式使用堆栈的链表实现来生成迷宫的解决方案。迷宫是从 .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;
            }
        }

在++ 之前执行 [ 的问题:

感谢任何帮助，谢谢!

Answer 1

您的算法在某些具有圆形路径的迷宫中不起作用:一旦您进入其中一个，您就会在原地打转。要解决此问题，您需要添加一个 bool 数组 visited[R][C][DIR]，其中 DIR 是一个从零到三的数字，表示一个方向。当您在 [d] 方向离开单元格 [r][c] 时，将 visited[r][c][d] 设置为 true。下次你访问同一个单元格时，看看你之前是否离开过同一个方向；如果你这样做了，跳过那个方向，然后继续下一个方向。