0

我的作业是确定不使用队列是否可以解决迷宫。如果是，打印路径。我可以让 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 二维数组。

maze1.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);
}
4

1 回答 1

1

队列为空并不能确定迷宫是否已解决。队列只是跟踪哪些空间仍然需要检查。来到迷宫的尽头，还有很多空间可以检查您的队列，这是非常好的。

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

于 2012-10-28T23:30:07.190 回答