数据结构课程设计迷宫求解.doc

考虑使用一个二维数组表示迷宫.所有的通路用0表示,墙用1表示,出口用9表示,入口用6表示,已经过点用3表示.输出走出迷宫的过程.
    从这个问题的求解过程中可以简单总结出两个算法,一是探路过程,二是输出路线.

1.探路过程
    探路过程算法可归纳为:
[1]从入口位置开始,检查东西南北四个方向上的通路,如果发现出口则成功退出,否则将所有通路坐标压入栈;
[2]从栈中取出一个坐标,将其标记为当前位置(标记数字3),再次判断通路情况;
[3]如此进行,直到发现出口则成功退出,若栈空而且未发现出口,则失败退出.
这里使用到的回溯过程可描述为: 每到达一点时,会将所有可能的通路坐标(标记数字0的节点)压入栈.所以当到达一点,而不存在可能的通路时,自然没有相应的坐标压入栈,而此时便从栈中取出上一个点所压入的可能的一个通路坐标,并继续作通路判断,这便是一个回溯的过程.

2.输出某一较短路线
    将所有在探路过程中经过的点(标记数字3的节点)按实际探路路线存入队列,对头为入口,队尾为出口.这些点可能存在绕路的情况,所以可用下面的算法输出某一较短路线.
[1]将队尾(出口)节点设置为当前判断节点;
[2]从当前判断节点(x,y)的前驱节点开始,向前遍历队列,如果发现相邻节点(其坐标可以为(x+1,y),(x-1,y),(x,y+1),(x,y-1)之一),则删除该相临节点至当前判断节点的前驱节点之间的所有节点;
[3]将该相临节点设置为当前判断节点,继续判断相临节点;
[4]当当前判断节点为对头节点时退出.

    该算法所得到的路线不一定是最短路线,想得到最短路线,可考虑使用树结构将所有由出口至入口的路线保留为一子树,树高最短的子树即为最短路线.但此算法可保证所得路线不会存在绕路情况.

3.表示节点坐标的类
public class MazeCell {
    private int x, y;//表示x轴y轴坐标

    public MazeCell() {
    }

    public MazeCell(int i, int j) {
        x = i;
        y = j;
    }

    public boolean equals(Object o) {
        if (!(o instanceof MazeCell))
            return false;
        MazeCell cell = (MazeCell) o;
        return cell.x == x && cell.y == y;
    }

    public String toString() {
        return x + "," + y;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }
}

4.所使用的栈数据结构
import java.util.LinkedList;

public class Stack {
    private LinkedList storage = new LinkedList();

    /** 入栈 */
    public void push(T v) {
        storage.addFirst(v);
    }

    /** 出栈，但不删除 */
    public T peek() {
        return storage.getFirst();
    }

    /** 出栈 */
    public T pop() {
        return storage.removeFirst();
    }

    /** 栈是否为空 */
    public boolean empty() {
        return storage.isEmpty();
    }

    /** 打印栈元素 */
    public String toString() {
        return storage.toString();
    }
}

5.求解迷宫问题
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class Maze {
    private int rows = 0, cols = 0;// 迷宫的行数与列数
    private char[][] store, path;// 迷宫矩阵
    private MazeCell currentCell, exitCell = new MazeCell(),
            entryCell = new MazeCell();// 当前节点,出口节点,入口节点
    private static final char EXIT = '9', ENTRY = '6', VISITED = '3';// 出口标记,入口标记,已经过节点标记
    private static final char PASS = '0', WALL = '1';// 通路标记,墙标记
    private StackzeCell> mazeStack = new Stack();// 探路过程所使用栈
    private List currentList = new LinkedList();// 路经的路线队列

    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 maze using the following"
                + " characters: \n6-entry\n9-exit\n1-wall\n0-passage\n"
                + "Enter one line at a time; end with Ctrl-d;");
        try {
            String str = buffer.readLine();
            while (str != null) {
                row++;
                cols = str.length();
                str = "1" + str + "1";
                mazeRows.push(str);
                if (str.indexOf(EXIT) != -1) {
                    exitCell.setX(row);
                    exitCell.setY(str.indexOf(EXIT));
                }
                if (str.indexOf(ENTRY) != -1) {
                    entryCell.setX(row);
                    entryCell.setY(str.indexOf(ENTRY));
                }
                str = buffer.readLine();
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        rows = row;
        store = new char[rows + 2][];
        store[0] = new char[cols + 2];
        for (; !mazeRows.empty(); row--)
            store[row] = (mazeRows.pop()).toCharArray();

        store[rows + 1] = new char[cols + 2];
        for (col = 0; col <= cols + 1; col++) {
            store[0][col] = WALL;
            store[rows + 1][col] = WALL;
        }
        path = new char[rows + 2][];
        copyArray(store, path);
    }

    /** 二维数组复制 */
    private void copyArray(char[][] src, char[][] tar) {
        for (int i = 0; i < src.length; i++) {
            tar[i] = new char[cols + 2];
            for (int j = 0; j < src[i].length; j++)
                tar[i][j] = src[i][j];
        }
    }

    /** 二维数组输出 */
    private void display(PrintStream out, char[][] carray) {
        for (int row = 0; row <= rows + 1; row++)
            out.println(carray[row]);
        out.println();
    }

    /** 将未访问并可通路的节点压入栈 */
    private void pushUnvisited(int row, int col) {
        if (store[row][col] == PASS || store[row][col] == EXIT)
            mazeStack.push(new MazeCell(row, col));
    }

    /** 探路过程 */
    public void exitMaze(PrintStream out) {
        currentCell = entryCell;
        currentList.add(currentCell);
        out.println();
        while (!currentCell.equals(exitCell)) {
            int row = currentCell.getX();
            int col = currentCell.getY();
            display(System.out, store);
            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.empty()) {
                display(out, store);
                out.println("Failure");
                return;
            } else {
                currentCell = mazeStack.pop();
                currentList.add(currentCell);
            }
        }
        display(out, store);
        out.println("Success");
    }

    /** 得到某一输出路线 */
    private void getPath() {
        if (currentList.size() <= 0)
            return;
        MazeCell cell = currentList.get(currentList.size() - 1);
        while (cell != currentList.get(0)) {
            List subList = currentList.subList(0, currentList
                    .indexOf(cell));
            ListIterator itr = subList.listIterator();
            while (itr.hasNext()) {
                MazeCell target = itr.next();
                if (adjoin(cell, target)) {
                    removeElements(currentList.indexOf(target) + 1, currentList
                            .indexOf(cell));
                    cell = target;
                    break;
                }
            }
        }
    }

    /** 删除队列中由from至to的连续元素 */
    private void removeElements(int from, int to) {
        int turn = to - from;
        while (turn > 0) {
            currentList.remove(from);
            turn--;
        }
    }

    /** 判断两个节点是否相邻 */
    private boolean adjoin(MazeCell current, MazeCell target) {
        if ((current.getX() == target.getX() + 1 || current.getX() == target
                .getX() - 1)
                && (current.getY() == target.getY()))
            return true;
        if ((current.getY() == target.getY() + 1 || current.getY() == target
                .getY() - 1)
                && (current.getX() == target.getX()))
            return true;
        return false;
    }

    /** 输出路线 */
    public void printPath(PrintStream out) {
        getPath();
        out.println("Path:");
        if (currentList.size() >= 2) {
            currentList.remove(currentList.size() - 1);
            currentList.remove(0);
        }
        Iterator itr = currentList.iterator();
        while (itr.hasNext()) {
            MazeCell cell = itr.next();
            path[cell.getX()][cell.getY()] = VISITED;
        }
        display(System.out, path);
    }

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

6.结果输出
Enter a rectangular maze using the following characters:
6-entry
9-exit
1-wall
0-passage
Enter one line at a time; end with Ctrl-d;
90000
11011
00000
00600
//构造的迷宫如下
1111111
1900001
1110111
1000001
1006001
1111111
//开始探路
1111111
1900001
1110111
1000001
1006001
1111111

1111111
1900001
1110111
1000001
1006301
1111111

1111111
1900001
1110111
1000001
1006331
1111111

1111111
1900001
1110111
1000031
1006331
1111111

1111111
1900001
1110111
1000331
1006331
1111111

1111111
1900001
1110111
1003331
1006331
1111111

1111111
1900001
1110111
1033331
1006331
1111111

1111111
1900001
1110111
1333331
1006331
1111111

1111111
1900001
1110111
1333331
1306331
1111111

1111111
1900001
1110111
1333331
1336331
1111111
//下一步为回溯过程
1111111
1900001
1110111
1333331
1336331
1111111

1111111
1900001
1113111
1333331
1336331
1111111

1111111
1903001
1113111
1333331
1336331
1111111

1111111
1903301
1113111
1333331
1336331
1111111

1111111
1903331
1113111
1333331
1336331
1111111
//下一步为回溯过程
1111111
1933331
1113111
1333331
1336331
1111111

Success
Path:
1111111
1933001
1113111
1003001
1006001
1111111