为什么我的递归方法基本情况没有返回应有的布尔值？

Question

我写了一个方法，通过堆栈和递归解决给定的文本编辑器迷宫，它解决了迷宫。然而，我的问题是，当给定的迷宫是不可解决的，因为迷宫的墙，它实际上是不可能解决的，这几乎就像我的基本情况被跳过了，没有返回false。这是代码

private boolean findPath(MazeLocation cur, MazeLocation finish) {
int row = cur.row;
int col = cur.col;
mazeToSolve.setChar(row, col, 'o');
fileWriter.println("n"+mazeToSolve.toString());
char strX = 'X';
char strH = 'H';
// First ,we need to scan the 4 directions around current location to see where to go
MazeLocation up = new MazeLocation(row-1, col);
MazeLocation down = new MazeLocation(row+1, col);
MazeLocation right = new MazeLocation(row, col+1);
MazeLocation left = new MazeLocation(row, col-1);
// BASE CASE - WHEN WE'VE REACHED FINISH COORDINATES
if(cur.row == finish.row && cur.col == finish.col){
return true;
}
// SECOND BASE CASE - IF MAZE ISNT SOLVABLE
if (path.isEmpty() == true){ // if the path is empty, then there is no solution.
return false;
}
// Check if we can go up
if(up.getRow() >= 0){
if(mazeToSolve.getChar(up.getRow(), up.getCol()) == ' '){
row = up.getRow();
col = up.getCol();
MazeLocation newCur = new MazeLocation(row, col);
path.push(newCur);
return findPath(newCur, finish);
}
}
// Check if we can go down
if(down.getRow() < mazeToSolve.getRows()){
if(mazeToSolve.getChar(down.getRow(), down.getCol()) == ' '){
row = down.getRow();
col = down.getCol();
MazeLocation newCur = new MazeLocation(row, col);
path.push(newCur);
return findPath(newCur, finish);
}
}
// Check if we can go right
if(right.getCol() < mazeToSolve.getCols()){
if(mazeToSolve.getChar(right.getRow(), right.getCol()) == ' '){
row = right.getRow();
col = right.getCol();
MazeLocation newCur = new MazeLocation(row, col);
path.push(newCur);
return findPath(newCur, finish);
}
}
// Check if we can go left
if(left.getCol() >= 0){
if(mazeToSolve.getChar(left.getRow(), left.getCol()) == ' '){
row = left.getRow();
col = left.getCol();
MazeLocation newCur = new MazeLocation(row, col);
path.push(newCur);
return findPath(newCur, finish);
}
}
// If we cant do any of the above then we need to backtrack by popping the top of stack
// and leaving X's until we can move up, down, left, or right again.
MazeLocation newCur = new MazeLocation(row, col);
path.pop(); // popping the cur where we are putting the x
mazeToSolve.setChar(row, col, 'x'); // putting the x
return findPath(path.top(), finish); // now we need to return to the position where the stack is NOW after the pop
}

正如你所看到的，有两种基本情况。一个答案是真的——迷宫解决了。另一个返回false——迷宫是无法解决的。我的isEmpty((方法的代码如下：

public boolean isEmpty() {
if(head == null){
return true;
}
return false;
}

它通过检查堆栈是否为空来返回false。例如，如果迷宫赛跑者撞到墙上并转身，它将在文本编辑器中留下一个x，如下所示：

0123456
0HHHHHHH
1ooooxxH
2HHHoHxH
3H  oHxH
4H HoHHH
5H Hoooo
6HHHHHHH

迷宫从6点5分开始；并且在0，1处结束。这是可以解决的。x代表一条失败的路线，o代表从开始到结束的路径。

在下一个迷宫示例中，无法完成代码从7,6开始的时间。

HHHHHHH
H
HHH H H
H   H H
H HHHHH
H H    
HHHHHHH

它会尝试向左移动两次，留下x，然后堆栈会弹出，直到没有堆栈，堆栈顶部指向null。但是我的基本情况代码被跳过了，它应该在尝试弹出空堆栈之前测试堆栈是否为空，如果是，则返回false。但事实并非如此。请帮忙吗？

Answer 1

首先，让我们先尝试理解问题语句。我们正在尝试使用深度优先的方法找到从源到目标的可能路径。

算法中有一个主要缺陷，那就是

// Check if we can go up
if(up.getRow() >= 0){
if(mazeToSolve.getChar(up.getRow(), up.getCol()) == ' '){
row = up.getRow();
col = up.getCol();
MazeLocation newCur = new MazeLocation(row, col);
path.push(newCur);
return findPath(newCur, finish);
}
}
// Check if we can go down
if(down.getRow() < mazeToSolve.getRows()){
if(mazeToSolve.getChar(down.getRow(), down.getCol()) == ' '){
row = down.getRow();
col = down.getCol();
MazeLocation newCur = new MazeLocation(row, col);
path.push(newCur);
return findPath(newCur, finish);
}
}

考虑我们当前处于点(2,2(，并且可以选择在4个方向中的任意一个方向上移动，即(1,2(、(3,2(、(1,3(和(2,1(。

按照你的逻辑。我们先向上移动(1,2(

可能有两种可能性。

1. 您从该点找到一条路径(返回true(
2. 您找不到路径，希望继续搜索其他三个选项。(返回false(

如果路径导致失败，您的代码当前将不会探索进一步的选项由于返回语句

return findPath(newCur, finish);

这个问题归结为在所有操作完成之前过早退出该方法。

以下堆栈清理必须在当前仅在其中一个场景中调用的方法的任何返回语句之前调用

// If we cant do any of the above then we need to backtrack by popping the top of stack
// and leaving X's until we can move up, down, left, or right again.
path.pop(); // popping the cur where we are putting the x

我仍然不完全理解这里显式堆栈的用法。因为递归解决了您试图使用堆栈解决的类似问题。然而我想就以下几点提出改进建议。

// Check if we can go up
if(up.getRow() >= 0){
if(mazeToSolve.getChar(up.getRow(), up.getCol()) == ' '){
row = up.getRow();
col = up.getCol();
MazeLocation newCur = new MazeLocation(row, col);
path.push(newCur);
boolean val =  findPath(newCur, finish);
if(val){
path.pop();
return true;
}
}
}