如何使用队列解决迷宫

Question

我对如何使用队列解决迷宫感到非常困惑。我提供了一些教授给我们的javadocs和一些psuedo代码。如果可能的话，请提供帮助。我看了其他话题，但我不明白，希望有人能帮我解决问题。感谢

public class QueueMazeSolver implements MazeSolver {
private MazeGUI gui;
public static class Cell {
    private int r;
    private int c;
    public Cell(int row, int col){
        r = row;
        c = col;
    }
}

public QueueMazeSolver(){
    gui = new MazeGUI( this );
}
/**
 * This method is called when the start button is
 * clicked in the MazeGUI.  This method should solve the maze.
 * This method may call MazeGUI.drawMaze(...) whenever the
 * GUI display should be updated (after each step of the solution).
 * 
 * The maze is provided as the first parameter.  It is a 2D array containing
 * characters that represent the spaces in the maze.  The following 
 * characters will be found in the array:
 *    '#' - This represents a wall.
 *    ' ' - This represents an open space (corridor)
 *    
 * When calling MazeGUI.drawMaze(...) to update the display, the GUI
 * will recognize the '#' and ' ' characters as well as the following:
 *    '@' - Means the cell is a space that has been explored
 *    '%' - Means that the cell is part of the best path to the goal.
 * 
 * @param maze the maze (see above).
 * @param startR the row of the start cell.
 * @param startC the column of the start cell.
 * @param endR the row of the end (goal) cell.
 * @param endC the column of the end (goal) cell.
 */
@Override
public void solve(char[][] maze, int startR, int startC, int endR, int endC) {
    maze[startR][startC] = '@';
    ArrayQueue<Cell> agenda = new ArrayQueue<Cell>();
    Cell temp = new Cell(startR, startC);
    agenda.offer(temp);
            // while agenda is not empty and red not found
    while(!agenda.isEmpty() && maze[endR][endC] != '@' ){
        Cell current = agenda.poll(); //remove front square from queue
        /*
        if front square is red
            found it
        else 
            mark amaze all unexplored neighbors of front
            square and add them to the square
        */
        if(current == new Cell(endR, endC) ){
            break;
        }
        else{
            =
            }
        }
        /** Notes
        maze[r][c] = '@' //marking cell seen
        up = r-1, c
        down = r+1, c
        left = r, c-1
        right = r, c+1
        */

    }
    if (!agenda.isEmpty())
            gui.setStatusText("Maze is solvable");
    else
        gui.setStatusText("Maze is unsolvable");

    gui.drawMaze(maze);
    try {Thread.sleep(150);}
    catch (InterruptedException e){
        System.err.println("Thread interrupted");
    }       
 }
public static void main(String[] args){
    QueueMazeSolver solver = new QueueMazeSolver();
   }
     }

Answer 1

你似乎正在试图找到在迷宫中移动的可能路径，并到达有墙（无法穿过）或开放空间的red细胞。

基本上，此代码应用广度优先搜索
我们从queue移除一个小区，并且如果周围的小区[at distance 1 unit]没有被访问，则将它们添加到queue并访问它们
伪代码（来自维基百科）：

1  procedure BFS(G,v) is
2      create a queue Q
3      create a vector set V
4      enqueue v onto Q
5      add v to V
6      while Q is not empty loop
7         t ← Q.dequeue()
8         if t is what we are looking for then
9            return t
10        end if
11        for all edges e in G.adjacentEdges(t) loop
12           u ← G.adjacentVertex(t,e)
13           if u is not in V then
14               add u to V
15               enqueue u onto Q
16           end if
17        end loop
18     end loop
19     return none
20 end BFS

假设您在小区(i,j)，因此t=(i,j)，并且相邻边（t）是(i+1,j)、(i,j+1)、(i-1,j)。(i,j-1)如果(i+1,j)以前没有被访问过，请将其添加到队列中（所以，下次从队列中弹出时，您会得到它）；否则，如果它被访问过（即在V中），则我们就完成了它。对其他三个单元格重复相同操作。

通过这种方式，您可以执行O(m*n)操作并访问每个单元格一次。