在Java中使用隊列解決迷宮問題

Question

我的作業是確定迷宮是否可以不使用隊列。如果是，則打印路徑。我可以讓Queue得到最終結果，但它說它無法解決。實際上它是。如果我改變了最終檢查if語句：

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

然後它說，這是可以解決的，但後來當我嘗試另一種迷宮，是不是可以解決它說，這是可以解決的。不知道我哪裏錯了。

我有一個單獨的Point類，它定義了Points和Right，Left，Above和Below位置。我必須使用Point（0,0）來標記起點和Point（第1行，第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 . 

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))被觸發，那麼迷宮是可以解決的。