首页 文章

使用堆栈记录迷宫路径解决方案

提问于
浏览 次
1

我将以某种方式使用堆栈的链表实现来生成迷宫的解决方案 . 迷宫是从.txt文件读入的，包含0 845213_ s用于墙 .
enter image description here
< - 很确定退出必须在底行？那么这三个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;
            }
        }

执行问题[之前：
enter image description here

任何帮助表示感谢，谢谢！

c++ algorithm stack maze

2 回答

  • 2

    你的算法在某些具有圆形路径的迷宫中不起作用：一旦你进入其中一个，你就会进入圆圈 . 要解决此问题，您需要添加一个布尔数组visited [R] [C] [DIR]，其中DIR是一个从0到3的数字，表示方向 . 将单元格[r] [c]保留在方向[d]时，将访问[r] [c] [d]设置为true . 下次您访问同一个单元格时，看看之前是否已将其保持在同一方向;如果你这样做，跳过那个方向，然后去下一个方向 .

    回复于
  • 0

    ++ 和 -- 实际上修改了行/列变量 . 我想你想做 maze[row - 1][col] == 0 然后一旦你搬家，更新你的行位置 .

    回复于

相关问题