maze.java

迷宫的队札算法

import java.io.*;
import java.util.Stack;

/**
 * <p>Title: </p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2007</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
public class Maze {
    private int rows = 0, cols = 0;
    private char[][] store;
    private MazeCell currentCell, exitCell = new MazeCell(), entryCell = new
            MazeCell();
    private final char exitMarker = 'e', entryMarker = 'm', visited = '.';
    private final char passage = '0', wall = '1';
    private Stack mazeStack = new Stack();

    public Maze() {
        int row = 0, col = 0;
        Stack mazeRows = new Stack();
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader buffer = new BufferedReader(isr);
        System.out.println("Enter a rectangular mae using the folowing " +
                           "characters:\nm - entry\ne - exit\n1 - wall\n0 - passage\n" +
                           "Enter one line at time; end with Ctrl-z:");
        String str = null;
        try {
            str = buffer.readLine();
        } catch (IOException ex1) {
        } 
        while (str != null) {
            row++;
            cols = str.length();
            str = "1" + str + "1";
            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);
            }
            try {
                str = buffer.readLine();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }
        rows = row;
        store = new char[rows + 2][];
        store[0] = new char[cols + 2];
        for (; !mazeRows.isEmpty(); row--)
            store[row] = ((String) mazeRows.pop()).toCharArray();
        store[rows + 1] = new char[cols + 2];
        for (col = 0; col <= col + 1; col++) {
            store[0][col] = wall;
            store[row + 1][col] = wall;
        }
    }

    private void display(PrintStream out) {
        for (int row = 0; row <= row + 1; row++) {
            out.println(store[row]);
        }
        out.println();
    }

    private void pushUnvisited(int row, int col) {
        if (store[row][col] == passage || store[row][col] == exitMarker)
            mazeStack.push(new MazeCell(row, col));
    }

    private void exitMaze(PrintStream out) {
        currentCell = entryCell;
        out.println();
        while (!currentCell.equals(exitCell)) {
            int row = entryCell.x;
            int col = entryCell.y;
            display(System.out);
            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");
    }

    public static void main(String[] args) {
        Maze maze = new Maze();
        maze.exitMaze(System.out);
    }
}


class MazeCell {
    public int x, y;
    public MazeCell() {

    }

    public MazeCell(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public boolean equals(Object obj) {
        return x == ((MazeCell) obj).x && y == ((MazeCell) obj).y;
    }
}