Что случилось с моей проверкой лабиринта ??? (JAVA)

Question

Итак, нам дают лабиринт со стенкой (W) открытой дорожкой (O) начальный pt (S) и финиш pt (F).

Я пытаюсь написать алгоритм, который берет файл лабиринта, а затем превращает его в 2D-массив точек, чтобы создать сетку.

Как только у меня есть сетка, я хочу начать с символа «S» в лабиринте и попытаться найти, можно ли пройти через O, чтобы добраться до F. (Вернуть булевское значение true/false)

Я знаю, что этот лабиринт разрешим, так почему я получаю «ложь» ?? Там должно быть проблемой, потому что усложнять все, что я получаю равнину логическое значение ложь, а не «извините, лабиринты Isnt проходимой» ...

Вот файл Maze1.txt:

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW 
WSOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOOOWOOOOOOOOOOOOOOOWOOOOOOW 
WWOOOOOOOOOOOOOWWWWWWWWWWWWWOOOOOOOOOOWWWWWWWWWWWWWOOOOOOW 
WWWWWWOOOOOOOOOOOOWWWWWWWOOOOOOOOOOOOWWWWWWWWWWWWWWWWOOOOW 
WOOOOOOWWWWWWWWWWWWWWOOOOOOOOOOOWWWWWWWWOOOOOOOOOOOOOOOWWW 
WOOOOWWWWWWWOOOOOOWWWWOOOOOOWWWWWWWWWWWOOOOWWWWWWWWWOWWWWW 
WOOOWWWWWWWWWWWWOOWWWWWWWWWWWWOOOOOOOOOOOOWWWWWWWWWOOOOOWW 
WOOWWWWWWWWWWWWWOOWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWWOOOW 
WOWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWOOOOOOOWWWWWWWWWWWOOW 
WOWWWWWWWWWWWWWOOOOOOOOOOOOOOOOOOOOOOOOOOOOWWWWWWWWWWWWOOW 
WOOOOOOOOOOOOOOOOWWWWOOOOOOOOWWWWWWWOOOOOOWWWWWWWWWWWWWOFW 
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW 

Вот мой код (новая попытка):

import java.io.File; 
import java.io.FileNotFoundException; 
import java.util.HashSet; 
import java.util.Scanner; 
import java.util.Stack; 
import java.awt.Point; 

public class MazeExplorer { 
    static Point startPoint = new Point(); 
    static Point finishPoint = new Point(); 
    final static int mazeHeight = 12; 
    final static int mazeWidth = 58; 
    static char[][] mazePoints = new char[mazeHeight][mazeWidth]; 
    Stack<Point> pointsNotTraversed = new Stack<Point>(); 
    Point pt = new Point(); 
    static HashSet<Point> previousLocations = new HashSet<Point>(); 
    static Stack<Point> nextPoints = new Stack<Point>(); 

    public static void main(String[] args) throws FileNotFoundException{ 

     System.out.println("Please enter the file name of your Maze"); 
     Scanner console = new Scanner(System.in); 
     File f = new File(console.nextLine()); 
     Scanner sc = new Scanner(f); 

     if(!sc.hasNextLine()){ 
      System.out.println("Sorry, please enter a file name with the extension, that contains a maze!"); 
     } 
     System.out.println("So, you want to know if your maze is solvable.....?"); 

     for (int row = 0; row < mazeHeight && sc.hasNext(); row++) { 
      final String mazeRow = sc.next(); //Get the next row from the scanner. 
      mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[]. 
     } 
      //identify the finish point 
     for(int i = 0; i < mazeHeight; i++){ 
      for(int j = 0; j<mazeWidth; j++){ 
       if(mazePoints[i][j] == 'F'){ 
        finishPoint = new Point(i, j); 
       }  
      } 
     } 
     // Identify the start point 
     for(int i = 0; i< mazeHeight; i++){ 
      for(int j = 0; j < mazeWidth; j++){ 
       if(mazePoints[i][j] == 'S'){ 
       startPoint = new Point(i , j); 
       } 
      } 
     } 
     isTraversable(startPoint);  
    } 
     public static boolean isTraversable(Point current){ 
      boolean isSolvable = false; 
      do { 
       mazePoints[current.x][current.y] = ' '; 

       if (mazePoints[current.y - 1][current.x] == 'O'){ //up dir 
        nextPoints.push(new Point(current.y - 1, current.x)); 
        mazePoints[current.y - 1][current.x] = ' '; //'X' marks where you've already been   
       } 
       if(mazePoints[current.y + 1][current.x] == 'O'){ // below direction 
        nextPoints.push(new Point(current.y + 1, current.x)); 
        mazePoints[current.y + 1][current.x] = ' ';   
       } 
       if(mazePoints[current.y][current.x + 1] == 'O'){ // to the right 
        nextPoints.push(new Point(current.y, current.x + 1)); 
        mazePoints[current.y][current.x + 1] = ' '; 
       } 
       if(mazePoints[current.y][current.x - 1] == 'O'){ // to the left 
        nextPoints.push(new Point(current.y, current.x - 1)); 
        mazePoints[current.y][current.x - 1] = ' ';    
       } 
       if(mazePoints[current.y][current.x] == 'F'){ 
        isSolvable = true; 
        System.out.println("MAZE IS SOLVABLE, YAHOOOOOO!!!!"); 
       } 
       current = nextPoints.peek(); 
       nextPoints.pop(); 
       isTraversable(current);   
      } while(!current.equals('F') && !nextPoints.isEmpty());   
      return isSolvable;   
     } 
} 

Answer 1

Вот алгоритм:

do 
    mark current spot in the array as "visited" (can use any symbol you want) 
    push all of the neighbors not yet visited onto the stack 
    current spot <-- top of the stack to visit the next spot 
    pop the stack 
while (exit is not found && stack is not empty) 

Просто написал это в течение 5 мин, пусть я знаю, есть ли ошибки.

EDIT (относительно редактирования параметров порядка):

Ваши canMove<direction> методы слишком сложны, нет на самом деле нет необходимости о делать такие функции, гораздо меньше, проверить стек. Кроме того, либо ваша функция traverseMaze должна принимать аргумент row и col для начальной позиции, либо вы должны помещать такую ​​информацию в свой класс как частные переменные.

Просто сделать что-то вроде

//assuming that current spot is at r,c 
if (mazePoints[r-1][c] == 'O'){ //up dir 
    pointsInMaze.push(new Point(r, c)); 
    mazePoints[r-1,c] = ''; //empty char marks where you've already been 
} 
//other directions ommitted here 

Теперь все, что вам нужно сделать, это поставить выше в цикл в алгоритме при условии, и он должен работать. Обратите внимание, что я изменил «текущее пятно метки в массиве как« посещенную »строку, чтобы« пометить соседей как посещенных »здесь, потому что проверка того, существует ли точка внутри стека, неэффективна. Гораздо проще просто пометить их как посещенных, как вы их нажимаете . в стек Однако, вам все еще нужно отметить свое исходное положение, как посетили, когда вы начинаете свой цикл

Answer 2

Другая мысль, используя стек код

псевдо:.

push starting point to path stack 
lastStepValid = true 
while (stack is not empty && goal not found) { 
    lastStep = peek the top of path stack 


    if (lastStep == goal) { 
     goal found = true 
    } else if (not lastStepValid) { 
    leave last step poped 
    if (path stack is not empty) { 
     pop path stack 
     lastStepValid = true 
     if (lastStep is UP of top of path stack) { 
      push RIGHT of top of path stack to path stack 
     } else if (lastStep is RIGHT of top of path stack) { 
      push DOWN of top of path stack to path stack 
     } else if (lastStep is DOWN of top of path stack) { 
      push LEFT of top of path stack to path stack 
     } else { 
      lastStepValid = false 
     } 
    } 
    } else if (lastStep is wall || lastStep exists more than once in the stack) { 
     lastStepValid = false; 
    } else { // last step is valid 
     push the UP of lastStep to path stack 
    } 
} 

вкратце, у вас есть стек, чтобы сохранить пройденный вами путь, и попробуйте каждый шаг в последовательности вверх, вправо, влево.

Этот подход не требует, чтобы вы отмечали ячейки в лабиринте.

Answer 3

Вы спрашивали в комментариях к вашему вопросу, как найти отправную точку. Вы можете найти отправную точку в процессе инициации вашего mazePoints массива

Stack<Point> stack = new Stack<Point>(); 
    Point start; 
    File f = new File("Maze1.txt"); 
    final Scanner sc = new Scanner(f); 
    for (int row = 0; row < mazeHeight && sc.hasNext(); row++) { 
     final String mazeRow = sc.next(); //Get the next row from the scanner. 
     mazePoints[row] = mazeRow.toCharArray(); //Convert the row into a char[]. 
     for (int i = 0; i < mazeRow.length(); i++) { 
     if (mazeRow.charAt(i) == 'S') { 
      start = new Point(row, i); 
      stack.push(start); 
      break; 
     } 
     } 
    } 

После инициализации, выполните один из алгоритмов, которые предусмотрены выше.