Бесконечная петля, когда мой стек пуст

Question

Я пытаюсь использовать Stack (Depth First Search), чтобы решить лабиринт. У меня есть несколько вопросов, кроме основной проблемы, которая в настоящее время я получаю бесконечный цикл, когда мой стек становится пустым. У меня есть хорошее понимание того, что мне нужно делать. У меня просто возникают проблемы с его применением к моему коду.

Я следую этому алгоритму для решения лабиринтов:

1.Create пустых стек

2.Search массив для исходного местоположения.

3.Place отправной точкой на стек

4.Remove точку из стека

5.Test, чтобы увидеть, если эта точка является отделка (если она есть, конец цикла)

6.Otherwise, отметить место в лабиринте, как оценивается, чтобы показать тракт

7.Проверьте пятна в лабиринте, которые являются соседними с текущим местоположением (вверх, вниз, влево, вправо).

8.Если они не являются стенами и еще не были оценены, добавьте эти точки в стек, чтобы определить другие местоположения.

Решить метод с методами Helper (большинство ошибок в 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

Вы не можете выскочить из или заглядывать в верхней части пустого стека. Поэтому для реализации стека должен быть предикат (метод boolean isEmpty()) для проверки того, пуст ли пуст. Код, который заглядывает в стек или появляется из стека, должен использовать этот предикат и обрабатывать случай с пустым стеком как особый случай или должен быть написан таким образом, чтобы гарантировать, что он никогда не манипулирует пустым стеком. Последнее на практике сложнее и реже.

Но что должен делать метод pop или peep из стека, если он is вызвал пустой стек? То есть, если метод был вызван с ошибкой? Метод должен сигнализировать об ошибке, бросая подходящее исключенное исключение. Это облегчит отладку ошибки. Является ли стек пустым, является частью информации о состоянии, если стек. Таким образом, стек находится в состоянии, которое недопустимо для метода pop или peek. Таким образом, наиболее подходящим является IllegalStateException.

Answer 2

Ваш цикл изменяет переменную цикла (test) к ложным, если вы найти путь (но эффект не имеет никакого значения, потому что вы можете вернуться из метода.

Ваш цикл не имеет и не изменить переменную цикла в других случаях . Установите test ложь, если все пути сделаны, и никто не будет успешным.

Или просто не проверить логическую переменную, но пустота стека в вашем выражении петли (while (!stack.isEmpty())).

Answer 3

3.Place начальный точка на стек

4.Удалить точку из стека

Уверены ли вы, что это действительно хорошая идея?

Answer 4

Я попытался исправить логические ошибки в вашем коде. Следующий код должен работать, но он не поместит ваши маркеры по желанию:

public static boolean solveDFS(char [][] maze){ 
    LinkedStack stack = new LinkedStack(); 
    Point startLoc = findPoint(maze,'s'); 
    Point finishLoc = findPoint(maze, 'f'); 
    stack.push(startLoc); 
    while (!stack.isEmpty()) { 
     Point curr = stack.pop(); 
     if(curr.equals(finishLoc)) { 
      printMaze(maze); 
      return true; 
     } else { 
      Point[] neighborSpots = getNeighborSpots(curr); 
      for(Point evaluate: neighborSpots) { 
       if(validSpot(stack, maze)) { 
        placeMarker(stack, maze); 
        stack.push(evaluate); 
        removeMarker(stack, maze); 
       } 
      } 
     } 
    } 
    return false; 
}