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

我要以某种方式使用链接列表实现堆栈来生成迷宫的解决方案。迷宫从.txt文件读入，由0表示开放空间，1表示墙壁。 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

赞赏任何帮助，谢谢！

来源

2011-11-30 darko

递归是你的朋友在这一个。 – Erix

您有具体问题吗？ –

我不认为这个算法特别好，例如，如果你在水平隧道中碰到右边的墙，你会永远从右到左反弹。 –

你的算法在某些具有循环路径的迷宫中将不起作用：一旦你进入其中一个迷宫，你将进入循环。为了解决这个问题，你需要添加一个布尔数组visited [R] [C] [DIR]，其中DIR是一个从0到3的数字，代表一个方向。在[d]方向离开单元格[r] [c]时，将visited [r] [c] [d]设置为true。下一次你访问同一个单元格时，看看你之前是否把它放在同一个方向上;如果你这样做，跳过这个方向，然后去下一行。

来源

2011-11-30 02:26:27 dasblinkenlight

嗯，我想我得到了访问阵列工作，但我遇到问题。有没有更好的方法来实现它在if语句这里是问题：http：//imgur.com/5rstN，右，下，右，右，击中墙然后转身并卡住。这里是我的新代码：http：//pastebin.com/uhp9MKfc – darko

@mwmnj检查你是否在某个地方的代码看起来不错，现在你需要实现回溯，一个奇特的名字为“当你做什么'重新卡住'。在你的情况下，你需要从rowStack/colStack中弹出最后一步，返回到前一个单元格，并继续下一个你以前没有尝试过的方向。 – dasblinkenlight

hmm，我最初的想法是在末尾添加一个else：'else {// if stuck rowStack.pop（）; colStack.pop（）; row = rowStack.top（）; col = colStack.top（）; '但现在看起来所做的一切就是将每一个先前的步骤从栈顶弹出，直到它变空为止 – darko

++和--实际上修改了行/列变量。我认为你想要做maze[row - 1][col] == 0，然后一旦你移动，更新你的排名。

来源

2011-11-30 02:22:25

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

回答

相关问题