Java迷宫

今天我们用简单的函数调用实现一个迷宫，具体操作如下：

迷宫的功能描述

1.提示“请输入迷宫的行列数:5 5”

2.提示“请输入迷宫的路径信息（0是可以行走，1是不能行走）:”
0 0 1 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
1 0 0 0 0
搜索迷宫路径…
3.若不存在路径则打印“迷宫不存在有效路径”
4. 若存在路径则再次打印迷宫，把是路径的地方用 * 打印出
* * 1 1 1
1 * 0 0 1
1 * 1 1 1
1 * 1 1 1
1 * * * *

迷宫功能分析
0 0 1 1 1
1 0 0 0 1
1 0 1 1 1
1 0 1 1 1
1 0 0 0 0

首先用在主函数中创建一个迷宫对象，通过二维数组生成迷宫，定义迷宫的行列数和迷宫信息！

public class Main {
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        System.out.print("请输入迷宫的行列数：");
        int row = in.nextInt();
        int col = in.nextInt();

        //用row 和 col生成迷宫对象
        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 = in.nextInt();
                maze.creatMazeNode(data,i,j);
            }
        }
        //设置迷宫每一个节点的四个方向的行走状态
        maze.setMazeNodeState();
        //开始寻找迷宫路径
        maze.findMazePath();
        //输出迷宫路径结果
        maze.showMazePath();
    }
}

解决这个问题需要创建一个栈，将入口处节点放入栈顶，规定在每一个节点处寻找迷宫路径按照右下左上的方式寻找，依次走过每一个节点，将可行走路径的节点放入栈中，最终将栈中元素输出，并打印出迷宫状态！

package 迷宫;
import java.util.Arrays;

/**
 * 顺序栈
 * 寻找迷宫路径需要用到的栈结构
 */
public class Stack {
    //存储节点类型
    private Node[] array;
    //栈顶的位置
    private int top;

    //构造，push,pop,top,full,empty
    public Stack(){//定义顺序栈的长度
        this.array = new Node[10];
        this.top = 0;
    }
    public void push (Node node){//构造节点入栈
        if (this.top==this.array.length){//判断数组元素是否溢出，若溢出则对其进行扩容
            this.array=Arrays.copyOf(this.array,this.array.length*2);
        }
        this.array[this.top++]=node;
    }
    public Node pop(){//将不符合条件节点进行出栈操作
        this.top--;
        Node node=this.array[top];
        return node;
    }
    public Node top(){
        return this.array[top-1];
    }//构造栈顶
    public boolean empty(){
        return this.top == 0;
    }//判断其是否为空
    public boolean full(){
        return this.array.length == this.top;
    }//判断栈满

}

因为迷宫的生成是一个二维数组，所以用一个Node函数来记录迷宫的节点类型和元素值，并且记录节点四个方向的行走状态。

package 迷宫;

/**
 * 迷宫节点的类型
 */
public class Node {
    int data;//节点值
    int x;//节点的x坐标
    int y;//节点的y坐标
    //记录节点四个方向的行走状态
    boolean right;
    boolean down;
    boolean left;
    boolean up;

    public Node(int data, int i, int j) {
        this.x=i;
        this.y=j;
        this.data=data;
    }
}

最终构造函数，完成迷宫的相应功能！

1.四个方向的行走状态代码实现

/**
     *
     * @param data
     * @param i
     * @param j
     */
    public void creatMazeNode(int data, int i, int j) {
        this.maze[i][j]=new Node(data,i,j);
    }
    //设置迷宫每一个节点的四个方向的行走状态
    public void setMazeNodeState() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (this.maze[i][j].data==1){
                    continue;
                }
                //调整节点的右方向
                if (j < col-1 && this.maze[i][j+1].data == 0){
                    this.maze[i][j].right=true;
                }
                //调整节点的下方向
                if (i<row-1 && this.maze[i+1][j].data == 0){
                    this.maze[i][j].down=true;
                }
                //调整节点的左方向
                if (j>0 && this.maze[i][j-1].data == 0){
                    this.maze[i][j].left=true;
                }
                //调整节点的上方向
                if (i>0 && this.maze[i-1][j].data == 0){
                    this.maze[i][j].up=true;
                }
            }
        }
    }

2.寻找迷宫路径代码实现

public void findMazePath() {
        if (maze[0][0].data == 1 || maze[row-1][col-1].data ==1) {//若起点和终点处节点元素为1，则返回值
            return;
        }
        //把入口节点入栈
        this.stack.push(this.maze[0][0]);
        while (!this.stack.empty()){//判断顺序栈是否为空
            //获取栈顶节点
            Node node=this.stack.top();
            //栈顶节点是出口节点，迷宫路径搜索完成了
            if (node.x ==row-1 && node.y ==col-1) {
                return;
            }
            if (node.right){//右方向可以走
                this.maze[node.x][node.y].right=false;
                this.maze[node.x][node.y+1].left=false;
                this.stack.push(this.maze[node.x][node.y+1]);
                continue;
            }
            if (node.down){//下方向可以走
                this.maze[node.x][node.y].down=false;
                this.maze[node.x+1][node.y].up=false;
                this.stack.push(this.maze[node.x+1][node.y]);
                continue;
            }
            if (node.left){//左方向可以走
                this.maze[node.x][node.y].left=false;
                this.maze[node.x][node.y-1].right=false;
                this.stack.push(this.maze[node.x][node.y-1]);
                continue;
            }
            if (node.up){//上方向可以走
                this.maze[node.x][node.y].up=false;
                this.maze[node.x-1][node.y].down=false;
                this.stack.push(this.maze[node.x-1][node.y]);
                continue;
            }
            this.stack.pop();
        }
    }

3.显示迷宫路径代码实现

 public void showMazePath() {
        if (this.stack.empty()){
            System.out.println("迷宫不存在有效路径");
        }else {
            while (!this.stack.empty()){
                Node node = this.stack.top();
                this.maze[node.x][node.y].data = '*';
                this.stack.pop();
            }
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (this.maze[i][j].data=='*'){
                        System.out.print('*' + " ");
                    }else {
                        System.out.print(this.maze[i][j].data + " ");
                    }
                }
                System.out.println();
            }
        }
    }
}```