java - 迷宫求解器问题(出现堆栈溢出错误)

Question

因此，我们得到了一个迷宫，其中有墙壁(W)、开放路径(O)、起始点(S)和结束点(F)。

我正在尝试编写一种算法，该算法采用迷宫文件，然后将其转换为二维点数组以形成网格。

一旦我有了网格，我想从迷宫中的“S”字符开始，尝试找出是否可以遍历 O 到达 F。(返回 boolean 值 true/false )

我知道这个迷宫是可以解决的，那么为什么我会收到 StackOverFlowError..？

这是 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

由于以下原因，您收到堆栈溢出错误:

public static  boolean isTraversable(Point current){
        boolean isSolvable = false;
        Stack<Point> dumbPoints = new Stack<>(); // visited
        dumbPoints.push(current); // pt is now visited
        previousLocations.add(startPoint); // starts with the 'S' point
        while(!dumbPoints.isEmpty()){
            Point test = dumbPoints.pop();
            if(previousLocations.contains(test)){
                continue; // This gets called, and while loop skips to next iteration
            }
          /* None of this code matters right now, it never gets looked at */

        } // End of while loop

        isTraversable(current);
        return isSolvable;
        }

您将 startPoint 发送到 isTraversable() 方法中。在方法内部，它被称为current。然后，您将 current AKA startPoint 插入堆栈，然后将 startPoint 添加到 previousLocations 集中。

while 循环运行是因为 dumbPoints 不为空(您将 current AKA startPoint 放在那里)。

在 while 循环中，您创建一个新点 test 并将其设置为等于堆栈中的顶部项目(即 current，又名 startPoint).

您检查一下 if(previousLocations.contains(test)) 是否为 true，事实确实如此。您将 startPoint 添加到 previousLocations 设置的 3 行中。由于它确实包含 startPoint，因此它会继续执行 while 循环的下一次迭代。

下次进入 while 循环时，堆栈为空，因为您弹出了其中的唯一项目(test)。所以这次 while 循环没有被执行。

然后我们跳到 while 循环之后的下一行:

isTraversable(current);

这又重新开始了我刚才所说的一切。这将永远运行，直到您的计算机内存不足。因此你的错误。

建议我建议尝试不同的方法。我相信你昨天问了一个关于这个问题的问题，其他人建议将所有相邻点插入堆栈。我认为这是一个好主意。您可以将所有相邻的 O 插入堆栈，然后在这些点上递归调用 isTraversable 方法，而不是将当前项插入堆栈。这将持续下去，直到返回 true 或 false，然后您就会得到答案。

这可能是您可以使用的更简洁的方法之一，与您已经创建的代码相差不远。