使用堆棧錄製迷宮路徑解決方案

我要以某種方式使用鏈接列表實現堆棧來生成迷宮的解決方案。迷宮從.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

使用堆棧錄製迷宮路徑解決方案

回答

相關問題