请教DS问题:如何用Java实现迷宫问题?

Question

用队列呀，应该很好解决的。
学习的过程应该是自己思考吗，不要总想着原代码，原代码是能节省时间，不过总这样下去会产生依赖性的。呵呵，说了一堆没用的话，抱歉！

Answer 1

以前用C的代码用队列实现过,不过前段时间在DataStructure上面看见用Stack实现的,不过它不是8个方向走,是只有4个方向的,源代码如下:
//****************************  Maze.java  ******************************
import java.io.*;class MazeCell {
    int x, y;
    MazeCell() {
    }
    MazeCell(int i, int j) {
        x = i; y = j;
    }
    boolean equals(MazeCell cell) {
        return x == cell.x && y == cell.y;
    }
}class Maze {
    int rows = 0, cols = 0;
    char[][] store;
    MazeCell currentCell, exitCell = new MazeCell(), entryCell = new MazeCell();
    final char exitMarker = 'e', entryMarker = 'm', visited = '.';
    final char passage = '0', wall = '1';
    Stack mazeStack = new Stack();
    Maze() {
        int row = 0, col = 0;
        Stack mazeRows = new Stack();
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader buffer = new BufferedReader(isr);
        String str;
        System.out.println("Enter a rectangular maze using the following "
                + "characters:\nm - entry\ne - exit\n1 - wall\n0 - passage\n"
                + "Enter one line at at time; end with Ctrl-z (PC) or Ctrl-D (Unix):");
        try {
            str = buffer.readLine();
            while (str != null) {
                row++;
                cols = str.length();
                str = "1" + str + "1";  // put 1s in the borderline cells;
                mazeRows.push(str);
                if (str.indexOf(exitMarker) != -1) {
                    exitCell.x = row;
                    exitCell.y = str.indexOf(exitMarker);
                }       
                if (str.indexOf(entryMarker) != -1) {
                    entryCell.x = row;
                    entryCell.y = str.indexOf(entryMarker);
                }
                str = buffer.readLine();
            }
        } catch(IOException eof) {
        }
        rows = row; 
        store = new char[rows+2][];       // create a 1D array of char arrays;
        store[0] = new char[cols+2];      // a borderline row;
        for ( ; !mazeRows.isEmpty(); row--)
            store[row] = ((String) mazeRows.pop()).toCharArray();
        store[rows+1] = new char[cols+2]; // another borderline row;
        for (col = 0; col <= cols+1; col++) {
            store[0][col] = wall;         // fill the borderline rows with 1s;
            store[rows+1][col] = wall;
        }
    }
    void display(PrintStream out) {
        for (int row = 0; row <= rows+1; row++)
            out.println(store[row]);
        out.println();
    }
    void pushUnvisited(int row, int col) {
        if (store[row][col] == passage || store[row][col] == exitMarker)
            mazeStack.push(new MazeCell(row,col));
    }
    void exitMaze(PrintStream out) {
        int row = 0, col = 0;
        currentCell = entryCell;
        out.println();
        while (!currentCell.equals(exitCell)) {
            row = currentCell.x;
            col = currentCell.y;
            display(System.out);        // print a snapshot;
            if (!currentCell.equals(entryCell))
                 store[row][col] = visited;
            pushUnvisited(row-1,col);
            pushUnvisited(row+1,col);
            pushUnvisited(row,col-1);
            pushUnvisited(row,col+1);
            if (mazeStack.isEmpty()) {
                 display(out);          
                 out.println("Failure");
                 return;
            }
            else currentCell = (MazeCell) mazeStack.pop();
        }
        display(out);
        out.println("Success");
    }
    static public void main (String args[]) {
        (new Maze()).exitMaze(System.out);
    }
}