java - 如何用队列解决迷宫？

Question

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

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 cell ，该 cell 有墙壁(不能穿过)或开放空间。

基本上这段代码应用了一个 breadth first search .
我们从 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

假设你在 cell(i,j) ，因此 t=(i,j) 和 adjacentEdges(t) 是 (i+1, j) , (i,j+1) , (i-1,j) 。 (i,j-1)如果 (i+1,j) 之前没有被访问过，将它添加到队列中(这样，下次你从队列中弹出时，你会得到它)否则如果它被访问过(即在 V) 然后我们就完成了。对其他三个单元格重复相同的操作。

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