数据结构——迷宫问题_数据结构迷宫问题

一.题意说明

求迷宫问题（见实验4-17）的所有路径。分别使用栈、队列、递归算法等实现（至少三种方法）。要求迷宫地图大小可自定义，障碍物可随机生成。

题意分析：用二维数组定义迷宫大小，确定迷宫方向。迷宫通路为1，不通为0，随机分配0和1，构造迷宫。分别用栈、队列、递归方法求解迷宫路径。采用链表存储迷宫内数据。

二.算法设计与分析

首先确定迷宫的大小，用二维数组构造迷宫，并且规定方向0—3代表上下左右。Path方法存放路径。随机使用0和1填充迷宫，0为不可通过点，1为可通过点。记录好起点和终点。1.栈：用栈格式存储路径，首先判断是否为终点，是就直接输出。不是就循环，判断该点是否来过，来过就退至栈顶，换个方向重来，如果退至栈空则没有符合的路径。2.队列：类似用广度优先遍历算法：当该点没有可走的路的时候，则放入队列，如遇到思路则回退，如遇到终点，则完成迷宫。否则队列空，则表明没有通路。3.递归调用：该算法递归调用自身没有路时，就抛出异常退出循环打印路径。首先判断上下左右有没有终点，进行循环调用自身。如果没有终点，则看上下左右有没有道路，设置数字5代表走过的路径，9代表无相通的路径。如果本次调用所有条件都不满足，说明该方向的道路是死路，该层递归结束返回上一层继续查找其他方向的路。在第一层递归调用中，如果上述条件都不满足。说明迷宫没有出口，则程序正常退出，不会抛出异常。

三. 源码

1）确认迷宫的大小和方向

①  public class Path {

public int x, y; //存放横纵坐标

public int direction; //行走的方向,以0-3表示上下左右

public Path(int x, int y, int direction) //存放路径

{

this.x = x;

this.y = y;

this.direction = direction;

}

public Path()

{

this(0, 0, 0);

}

public boolean equals(Object obj)

{

if(super.equals(obj))

return true;

if(obj instanceof Path)

{

if(((Path)obj).x == this.x && ((Path)obj).y == this.y)

return true;

else

return false;

}

else

return false;

}

}

② public class Direction {

    private int x;

    private int y;

    public Direction(int x, int y) {

        this.x = x;

        this.y = 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;

    }

}

2）栈

public class CreateLabyrinth {

private Stack<Path> pathstack = new Stack<Path>(); //以栈格式存储Path

public int[][] labyrinth; //以二维数组构造迷宫

public int x, y;

    public static double rate0=0.05;

    public static double rate1=0.95;

    

public CreateLabyrinth(