我是 C 新手，正在嘗試撰寫一個程式來讀取檔案，動態創建一個二維陣列，并用來自檔案的輸入填充陣列。然后它使用遞回解決迷宮。文本檔案如下所示：
前 4 個數字表示行數、列數和起始位置 (X,Y)。“S”是起點，“O”是路徑，“E”是終點。我創建陣列或者填充陣列都沒有問題，但是在運行程式時，呼叫遞回函式解迷宮時遇到錯誤。這是功能：
bool mazeSolve(char **maze, int startRow, int startCol){
char test = maze[startRow][startCol];
//If maze finds end stop program (Base Case)
if (test == 'E'){
cout << "End reached" << endl;
return true;
}//End if for base case
//If function can go right
if (maze[startRow][startCol 1] == 'O'){
maze[startRow][startCol] = 'P';
return mazeSolve(maze, startRow, startCol 1);
}
//If function can go left
if (maze[startRow][startCol-1] == 'O'){
maze[startRow][startCol] = 'P';
return mazeSolve(maze, startRow, startCol-1);
}
//If function can go up
if (maze[startRow-1][startCol] == 'O' && startRow-1 >= 0){
maze[startRow][startCol] = 'P';
return mazeSolve(maze, startRow-1, startCol);
}
//If function can go down
if (maze[startRow 1][startCol] == 'O'){
maze[startRow][startCol] = 'P';
return mazeSolve(maze, startRow 1, startCol);
}
//If function cannot find O's then it will backtrack
//If function reaches wall, backtrack down
if (maze[startRow 1][startCol] == 'P'){
maze[startRow][startCol] = 'C';
return mazeSolve(maze, startRow 1, startCol);
}
//If function reaches wall, backtrack up
if (startRow-1 >= 0 && maze[startRow-1][startCol] == 'P'){
maze[startRow][startCol] = 'C';
return mazeSolve(maze, startRow-1, startCol);
}
//If function reaches wall, backtrack left
if (maze[startRow][startCol-1] == 'P'){
maze[startRow][startCol] = 'C';
return mazeSolve(maze, startRow, startCol-1);
}
//If function reaches wall, backtrack right
if (maze[startRow][startCol 1] == 'P'){
maze[startRow][startCol] = 'C';
return mazeSolve(maze, startRow, startCol 1);
}
我在這個網站上搜索過類似的問題，但我似乎對遞回有一個基本的誤解，因為我無法遵循解決方案。我認為下半部分將允許函式回溯，直到它找到一個新的“O”并最終找到一個“E”，但它是無限回圈的。我的教授要求使用 if 陳述句來完成此操作。我的邏輯哪里出錯了？任何幫助將不勝感激。
uj5u.com熱心網友回復：
經過一番除錯，我想通了。從頭開始重寫函式。謝謝大家的幫助。我添加了一個越界檢查，并為 if 陳述句添加了一個條件來檢查“O”和“E”。奇怪的是，如果陳述句保持不變，即使我認為它們是問題所在。：
bool mazeSolve(char **maze, int startRow, int startCol){
//Output test message
char test = maze[startRow][startCol];
//cout << test << endl;
//If maze finds end stop program (Base Case)
if (test == 'E'){
cout << "End reached" << endl;
return true;
}//End if for base case
//Out of bounds check
if (startRow < 0 || startCol < 0 || startRow >= arrayRowSize ||
startCol >= arrayColSize){
cout << "bounds error";
return false;
}//End out of bounds if
//If function can go down
if (maze[startRow 1][startCol] == 'O' || maze[startRow 1][startCol] == 'E'){
maze[startRow][startCol] = 'P';
//cout << "down" << endl;
return mazeSolve(maze, startRow 1, startCol);
} //End down if
//If function can go right
if (maze[startRow][startCol 1] == 'O' || maze[startRow][startCol 1] == 'E'){
maze[startRow][startCol] = 'P';
//cout << "right" << endl;
return mazeSolve(maze, startRow, startCol 1);
} //End right if
//If function can go left
if (maze[startRow][startCol-1] == 'O' || maze[startRow][startCol-1] == 'E'){
maze[startRow][startCol] = 'P';
//cout << "left" << endl;
return mazeSolve(maze, startRow, startCol-1);
} //End left if
//If function can go up
if (maze[startRow-1][startCol] == 'O' || maze[startRow-1][startCol] == 'E'){
maze[startRow][startCol] = 'P';
//cout << "right" << endl;
return mazeSolve(maze, startRow-1, startCol);
} //End up if
//If function cannot find O's then it will backtrack
//If function reaches wall, backtrack down
if (maze[startRow 1][startCol] == 'P'){
maze[startRow][startCol] = '*';
return mazeSolve(maze, startRow 1, startCol);
} //End backtrack down if
//If function reaches wall, backtrack up
if (maze[startRow-1][startCol] == 'P'){
maze[startRow][startCol] = '^';
return mazeSolve(maze, startRow-1, startCol);
} //End backtrack up if
//If function reaches wall, backtrack left
if (maze[startRow][startCol-1] == 'P'){
maze[startRow][startCol] = '<';
return mazeSolve(maze, startRow, startCol-1);
} //End backtrack left if
//If function reaches wall, backtrack right
if (maze[startRow][startCol 1] == 'P'){
maze[startRow][startCol] = '>';
return mazeSolve(maze, startRow, startCol 1);
//End backtrack right if
} else
return false;//If all else fails, maze is unsolvable
}
這解決了迷宮。如果迷宮沒有盡頭，我現在唯一的問題是錯誤處理。我將txt檔案編輯為沒有“E”，函式無限回圈。我認為最后的“其他”宣告會涵蓋這一點，但事實并非如此。我應該怎么做才能處理無法解決的迷宮的情況？
uj5u.com熱心網友回復：
當您回溯時，您首先檢查搜索是否成功，然后在恢復剛剛進行的嘗試后嘗試不同的選項。
您的第一個非基本案例的實際回溯變體如下所示：
if (maze[startRow][startCol 1] == 'O'){
auto original = maze[startRow][startCol];
maze[startRow][startCol] = 'P';
if (mazeSolve(maze, startRow, startCol 1))
return true;
maze[startRow][startCol] = original;
}
// ... and keep going with the next attempt ...
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/478710.html