java - 在 Java 中使用队列解决迷宫问题

Question

我的作业是确定迷宫是否可以在不使用队列的情况下解决。如果是，则打印路径。我可以让 Queue 到达末尾，但它说它无法解决。实际上是什么时候。如果我将 Final check if 语句更改为:

if (queue.isEmpty())
    {
        System.out.println("The maze is solvable!");
    }
else
    {
        System.out.println("The maze is unsolvable!");
    }

然后它说它是可解的，但是当我尝试另一个不可解的迷宫时，它说它是可解的。不知道我哪里错了。

我有一个单独的 Point 类，它定义了 Points 以及右、左、上、下位置。我必须使用 Point (0,0) 来标记起点，使用 Point (row-1,col-1) 来标记目标。

如果您需要更多代码，请告诉我。它正在搜索 char 二维数组。

ma​​ze1.txt - (第一行定义行数和列数) - 可解

7 12
..+.+.++++++
.++...++...+
..++.....+.+
+.+..++.+..+
+...++....++
+.+++..++..+
++++++++++..

说这是无法解决的

    QueueMaze
The maze is unsolvable!
p p + p + p + + + + + + 
p + + p p p + + p p p + 
p p + + p p p p p + p + 
+ p + p p + + p + p p + 
+ p p p + + p p p p + + 
+ p + + + p p + + p p + 
+ + + + + + + + + + p . 

m解决迷宫的方法

public void queueMaze() {

char[][] storedMaze = copy(); 

LinkedList<Point> queue = new LinkedList<Point>();
    int count = 0;
    Point start = new Point(0,0);
    Point cur, end, above, right, left, below;

    Boolean solved = false;

queue.add(start); 

while (!queue.isEmpty())
    {
    //Store the first element position 0 in cur
        cur = queue.removeFirst();
        //System.out.println(cur.toString());

        //compare cur's points to the isEnd points
        //(row-1, col-1) if it is the end, break out
        //of the While
        if (isEnd(cur) && isSafe(cur))
        {
            //System.out.println("cur's final : " + cur.toString());
            end = cur;
            break;
        }

        //mark cur as visited with a P
    markVisited(cur, P);

        //check the position above cur to see if it is
        //
    right = cur.getRight(); 
    if (inBounds(right) && isSafe(right))
        {
            queue.add(right);
        }

        below = cur.getBelow(); 
    if (inBounds(below) && isSafe(below))
        {
            queue.add(below);
        }

        left = cur.getLeft(); 
    if (inBounds(left) && isSafe(left))
        {
            queue.add(left);
        }

        above = cur.getAbove(); 
    if (inBounds(above) && isSafe(above))
        {
            queue.add(above);
        }

}//while
//System.out.println("The queue size is: " + queue.size());

    if (!queue.isEmpty())
    {
        System.out.println("The maze is solvable!");
    }
else
    {
        System.out.println("The maze is unsolvable!");
    }

print();

returnMaze(storedMaze);
}

Answer 1

队列是否为空并不能决定迷宫是否被解决。队列只是跟踪哪些空间仍需要检查。走到迷宫的尽头，还有很多空间可以 checkin 队列，这是完全可以的。

看起来如果你的 if (isEnd(cur) && isSafe(cur)) 被触发，那么迷宫就可以解决。