欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

迷宫算法(java实现)

程序员文章站 2024-03-04 09:42:29
...

迷宫问题是栈的典型应用,因此借助栈来实现迷宫问题;
*题目描述:用类来解决迷宫路径的查找问题,寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径,0代表可以行走,1代表不能行走,找到,请输入最终的迷宫和路径信息, 找不到,请输出不存在有路径。
例如:
* 请输入迷宫的行列数(m * n):5 5
* 请输入迷宫的路径:
* 0 0 1 0 0
* 1 0 0 1 0
* 0 1 0 1 0
* 0 0 0 1 0
* 0 0 0 0 0
* 正在寻找迷宫路径。。。
* 结果:
* 从左上角入口到右下角出口不存在有效路径 ;
* 路径已找到,输入如下(2代表行走的路径)
* 2 2 1 0 0
* 1 2 2 1 0
* 0 1 2 1 0
* 0 0 2 1 0
* 0 0 2 2 2
* /
* 实现该算法,共定义了四个类;
(1)首先给出栈的抽象数据类型结构:StackADT:主要包括入栈,出栈,判空,判满,取栈顶数据元素;

class SqStack{
    private MazeNode[] stack;
    private int top;

    public SqStack(){
        top = 0;
        stack = new MazeNode[50];
    }
    public void push(MazeNode node){
        if(full()){
            resize();
        }
        this.stack[++top]=node;
    }
    public void pop(){
        if(empty())
            return;
        top--;  
    }
    public MazeNode top(){
        return this.stack[top-1];
    }
    public boolean empty(){
        return this.top==0; 
    }
    public boolean full(){
        return this.top==this.stack.length;
    }
    private void resize(){
        stack=Arrays.copyOf(stack, stack.length*2);
    }
}

(2)迷宫类,包括整个迷宫行,列,结点;

class Maze{
    private int row;
    private int colum;
    private MazeNode[][] mazePath;
    private SqStack stack;

    public Maze(int row, int colum){
        this.row = row;
        this.colum = colum;
        mazePath = new MazeNode[this.row][this.colum];
        stack = new SqStack();
    }
    public void setPath(int i, int j, int value){
        mazePath[i][j] = new MazeNode(value, i, j);
    }
}

(3)结点类,包括结点的行列,结点的值,以及结点的状态;

public class MazeNode {
    private int value;
    private int i;
    private int j;
    private int[] pathState;   //四个结点状态;

    public MazeNode(int value, int i, int j) {
        this.value = value;
        this.i = i;
        this.j = j;

        // 初始化节点的四个方向的路径信息,都初始化成不能行走
        pathState = new int[Constant.WAY_NUMBER];
        for (int k = 0; k < pathState.length; ++k) {
            pathState[k] = Constant.WAY_DISABLE;
        }
    }
    //设置该结点的行走状态
    public void setPathState(int path, int state) {
         pathState [path]= state;
    }
    //获取该结点的状态
    public int[] getPathState() {
        return pathState;
    }
    //获取该结点的value值
    public int getValue() {
        return value;
    }
    //设置该结点的value值
    public void setValue(int value) {
        this.value = value;
    }
    public int getRow() {
        return i;
    }
    public void setRow(int i) {
        this.i = i;
    }
    public int getCol() {
        return j;
    }
    public void setCol(int j) {
        this.j = j;
    }
}

(4)constant(这个类主要是定义次项目中所用到的常量)

public class Constant {
    //表示方向总数;
    public static int WAY_NUMBER=4;
    //表示路径可以走;
    public static int WAY_ENABLE=1;
    //表示路径不可以走;
    public static int WAY_DISABLE=0;
     //表示迷宫结点 四个方向;
    public static final int WAY_EAST = 0;
    public static final int WAY_SOUTH = 1;
    public static final int WAY_WEST = 2;
    public static final int WAY_NORTH = 3;
}

实现该算法主要用到三个函数:
(1)maze.adjustMazePath(); //该函数主要用来更改迷宫节点四个方向的行走状态

public void adjustMazePath(){
        for(int i=0;i<row;i++){
            for(int j=0;j<colum;j++){
                if(mazePath[i][j].getValue()==0){    
                //东
  if(j<colum-1 && mazePath[i][j+1].getValue()==0 ){  //当前结点的东边结点为0,东边路径设为可以走;
        mazePath[i][j].setPathState(Constant.WAY_EAST, Constant.WAY_ENABLE);    
                }
                //南
 if(i<row-1&& mazePath[i+1][j].getValue()==0){   //当前结点的南边结点为0,南边路径设为可以走;
      mazePath[i][j].setPathState(Constant.WAY_SOUTH, Constant.WAY_ENABLE);
                }
       //西
     if(j>0 && mazePath[i][j-1].getValue()==0){  //当前结点的西边结点为0,西边路径设为可以走;
                    mazePath[i][j].setPathState(Constant.WAY_WEST, Constant.WAY_ENABLE);
                }
      //北
     if(i>0 && mazePath[i-1][j].getValue()==0){  //当前结点的北边结点为0,北边路径设为可以走;
    mazePath[i][j].setPathState(Constant. WAY_NORTH, Constant.WAY_ENABLE);      
                }
            }
        }
    }

}

(2)maze.findMazePath(); //开始寻找迷宫路径

public void findMazePath(){
        int i=0,j=0;
        stack.push(mazePath[i][j]);
        while(!stack.empty()){
            MazeNode top=stack.top();
if (top.getRow()==row-1 && top.getCol()==colum-1)   break;
        //东边可以走
        if(mazePath[top.getRow()][top.getCol()].getPathState()[Constant.WAY_EAST]== Constant.WAY_ENABLE){
        mazePath[top.getRow()][top.getCol()].setPathState(Constant.WAY_EAST, Constant.WAY_DISABLE); //当前结点的东设为不能走(不能再走回去)
        mazePath[top.getRow()][top.getCol()+1].setPathState(Constant.WAY_WEST, Constant.WAY_DISABLE); //东边结点的西设为不能走;
           stack.push(mazePath[top.getRow()][top.getCol()+1]);   //东边结点压入栈
                continue;   
            }
            //南边可以走
            else  if(mazePath[top.getRow()][top.getCol()].getPathState()[Constant.WAY_SOUTH]== Constant.WAY_ENABLE){
                mazePath[top.getRow()][top.getCol()].setPathState(Constant.WAY_SOUTH, Constant.WAY_DISABLE); //当前节点的南设为不能走;
                mazePath[top.getRow()+1][top.getCol()].setPathState(Constant.WAY_NORTH,  Constant.WAY_DISABLE);//南边结点的北设为不能走;
                stack.push(mazePath[top.getRow()+1][top.getCol()]);   //南边结点压入栈
                continue;

            }
            //西边可以走
            else  if(mazePath[top.getRow()][top.getCol()].getPathState()[Constant.WAY_WEST]== Constant.WAY_ENABLE){
                mazePath[top.getRow()][top.getCol()].setPathState(Constant.WAY_WEST, Constant.WAY_DISABLE);   //当前结点的西设为不能走
                mazePath[top.getRow()][top.getCol()-1].setPathState(Constant.WAY_EAST, Constant.WAY_DISABLE);  //西边结点的东设为不能走
                stack.push(mazePath[top.getRow()][top.getCol()-1]);  //西边结点压入栈
                continue;
            }
            //北边可以走
            else if(mazePath[top.getRow()][top.getCol()].getPathState()[Constant. WAY_NORTH]== Constant.WAY_ENABLE){
                mazePath[top.getRow()][top.getCol()].setPathState(Constant. WAY_NORTH, Constant.WAY_DISABLE); //当前节点的北设为不能走;
                mazePath[top.getRow()-1][top.getCol()].setPathState(Constant.WAY_SOUTH,Constant.WAY_DISABLE); //北边节点的南设为不能走;
                stack.push(mazePath[top.getRow()-1][top.getCol()]);   //北边结点压入栈
                continue;
            }
         stack.pop();   
        }
    }

(3)maze.showMazePath() ;//打印迷宫路径;

public void showMazePath(){
        while(!stack.empty()){  //栈非空,栈中元素即为找到的路径,将找到的路径改为2;
            MazeNode p=stack.top();
            mazePath[p.getRow()][p.getCol()].setValue(2);
            stack.pop();
        }
        System.out.println("迷宫路径已找到(2代表行走的路径)");
        for(int i=0;i<colum;i++){
            for(int j=0;j<row;j++){
                System.out.print(mazePath[i][j].getValue());
                System.out.print(" ");
            }
            System.out.println("\n");
        }
    }
  }

main函数

“`
public class TestMazePathDemo {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner scan = new Scanner(System.in);

    System.out.print("请输入迷宫的行列数(m * n):");
    int row = scan.nextInt();
    int col = scan.nextInt();

    //maze现在代表的就是整个迷宫对象
    Maze maze = new Maze(row, col);
    System.out.println("请输入迷宫的路径:");
    for(int i=0; i<row; ++i){
        for(int j=0; j<col; ++j){
            int data = scan.nextInt();
            maze.setPath(i, j, data);
        }
    }
    //以上代码,就把整个迷宫路径的信息都设置到maze对象里面了
    maze.adjustMazePath;
    System.out.println("正在寻找迷宫路径");
    maze.findMazePath();
    maze.showMazePath();
}

}
运行结果如下:
迷宫算法(java实现)