java - 当我的堆栈为空时无限循环

Question

我正在尝试使用堆栈(深度优先搜索)来解决迷宫。除了主要问题之外，我还遇到一些问题，即一旦我的堆栈变空，我当前就会陷入无限循环。我很清楚我需要做什么，只是在将其应用到我的代码中时遇到了困难。

我正在遵循这个算法来解决迷宫:

1.创建一个空栈

2.在数组中搜索起始位置。

3.将起点入栈

4.从堆栈中删除一个点

5.测试此时是否结束(如果是则结束循环)

6.否则，将迷宫中的点标记为评估以显示路径

7.检查迷宫中与迷宫相邻的点当前位置(上、下、左、右)。

8.如果它们不是墙，并且尚未被评估，则将这些点添加到堆栈中以作为其他要评估的位置。

使用辅助方法求解方法(大多数错误都在solveDFS()中)

    //Tries going up,down,left,or right from current location and
    //marks path if valid. The algorithm should finish when reaching
    //the finish spot
    public static boolean solveDFS( char [][] maze ){
    LinkedStack stack = new LinkedStack();
    Point startLoc = findPoint(maze,'s');
    Point finishLoc = findPoint(maze, 'f');
    stack.push(startLoc);

    Point[] neighborSpots = getNeighborSpots(startLoc);

    boolean test = true;
    while ( test ){
        stack.pop();
        if(stack.peek().equals(finishLoc)){
            printMaze(maze);
            test = false;
            return true;
        }else{
            for( Point evaluate : neighborSpots ){
                if( validSpot( stack, maze ) ){
                    placeMarker( stack, maze );
                    if( stack.peek().equals(evaluate)){
                        return true;
                    }
                    removeMarker( stack, maze);
                }
            }
        }
    }
    return false;
}
//Returns true of coordinates of free spot is valid or finish spot
//Should not be off edge of maze
private static boolean validSpot( LinkedStack spot, char [][] maze ){
    if ( spot.peek().x < 0 || spot.peek().x >= maze.length ||
            spot.peek().y < 0 || spot.peek().y >= maze[spot.peek().x].length ) {
        return false;
    }
    return ( maze[spot.peek().x][spot.peek().y] == ' ' || maze[spot.peek().x][spot.peek().y] == 'f' );
}
//Searches the array for a point
private static Point findPoint( char [][] maze, char c ) {
    for ( int i = 0; i < maze.length; i++ ) {
        for ( int j = 0; j < maze[i].length; j++ ) {
            if ( maze[i][j] == c ) {
                return new Point(i, j);
            }
        }
    }
    return null;
}
//returns an array containing coordinates of neighbor spots
private static Point[] getNeighborSpots( Point spot ) {
    Point[] neighborSpots = new Point[4];

    neighborSpots[0] = new Point(spot.x + 1, spot.y);
    neighborSpots[1] = new Point(spot.x, spot.y + 1);
    neighborSpots[2] = new Point(spot.x - 1, spot.y);
    neighborSpots[3] = new Point(spot.x, spot.y - 1);

    return neighborSpots;
}
//Marks the path by adding a '.'
private static void placeMarker( LinkedStack spot, char [][] maze ){
    maze[spot.peek().x][spot.peek().y] = '.';
}
//Removes marker from path by adding a blank space
private static void removeMarker ( LinkedStack spot, char [][] maze ) {
    maze[spot.peek().x][spot.peek().x] = ' ';
}

Answer 1

如果找到路径，循环会将循环变量 (test) 更改为 false(但效果无关紧要，因为您直接从方法返回。

在其他情况下，您的循环永远不会更改循环变量。如果所有路径均已完成且没有成功，则将 test 设置为 false。

或者干脆不测试 boolean 变量，而是测试循环表达式中堆栈的空性(while (!stack.isEmpty()))。