在Java中使用队列解决迷宫

Question

我的作业是确定迷宫是否可以解决不使用队列。如果是，请打印路径。我可以让队列结束，但它说这是无法解决的。何时实际。如果我将最终检查如果语句更改为：

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

然后说它是可以解决的，但是当我尝试另一个无法解决的迷宫时，它说它是可以解决的。不知道我要在哪里。

我有一个单独的点类，可以定义点和右，左，上方和下方的位置。我必须使用点（0,0）来标记起点（第1，col-1）以标记目标。

让我知道您是否需要更多代码。它正在搜索一个char 2d阵列。

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 . 

mmethod用于求解迷宫

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

排空的队列不能确定是否解决了迷宫。队列仅跟踪仍需要检查哪些空间。剩下很多空间要在您的队列中检查到迷宫的尽头是完全可以的。

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