Java 简单实现迷宫寻找路径

项目介绍

一个网格迷宫由n行m列的单元格组成，每个大院个要么是空地（用0表示），要么是障碍物（用1表示）。你的任务是找一条从起点到终点的移动序列，其中只能上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中，也不能走到迷宫之外。起点为左上角和终点右下角。

项目功能

解决迷宫路径查找问题，寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径，0代表可走，1代表不能行走，找到请输出最终的迷宫和路径信息，找不到请输出不存在有效路径

知识点

基础语法(if-else、for循环等）函数调用 封装二维数组Java面向对象思想构造函数this关键字使用非递归栈进行实现

实现思路

定义一个迷宫节点类型（MazeNode）的二维数组初始化每个格子中的value值。给二维数组每个格子存放对象。对象的value值只能为0（当前格子可以走）或者1（当前格子不能走）初始化每个格子四个方向（东南西北）是否是可走状态。根据当前节点周围四个方向格子中的value值，判断当前节点的东南西北四个方向是否可走（0是可走，1不可走）。开始走迷宫。采用栈操作，记录行走的路径，将左上角元素入栈，判断当前栈顶元素的哪个方向可走，将其中一个可走方向进行入栈操作，直到右下角元素停止。栈中保存走过的路径。 注意: 如果遇到走入死胡同问题，此时需要将是栈顶元素并且栈顶元素的四个方向都不能行走，此时将其出栈，选择新方向再次入栈，直到右下角元素停止。

源代码

1.测试类

public class Test { public static void main(String[] args) { Maze maze = new Maze(4,4); maze.initValue(); maze.initWayState(); maze.goMaze(); maze.show(); } }

2.迷宫节点类

public class MazeNode { private int x; private int y; private int value; public boolean way_east; public boolean way_west; public boolean way_north; public boolean way_south; public MazeNode(){ } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public int getX() { return x; } public int getY() { return y; } public void setX(int x) { this.x = x; } public void setY(int y) { this.y = y; } }

3.迷宫类

public class Maze { private MazeNode[][] mazeNodes; private int row; private int colum; MyStack myStack = new MyStack(); private static MazeNode mazeNode; //建立迷宫 public Maze(int row,int colum) { mazeNodes = new MazeNode[row][colum]; this.row = row; this.colum = colum; } //初始化迷宫路径 public void initValue(){ Scanner scanner = new Scanner(System.in); System.out.println("请输入迷宫路径:"); for(int i = 0;i<row;i++){ for(int j = 0;j<colum;j++){ //i j mazeNodes[i][j] = new MazeNode(); mazeNodes[i][j].setValue(scanner.nextInt()); mazeNodes[i][j].setX(i); mazeNodes[i][j].setY(j); } } } //初始化每个路的状态 public void initWayState(){ for(int i=0;i<row;i++){ for(int j = 0;j<colum;j++){ //i j if(mazeNodes[i][j].getValue() == 0){ // 东: 东边结点的value == 0 当前结点的东边方向是可走 if(j+1<colum && mazeNodes[i][j+1].getValue() == 0){ mazeNodes[i][j].way_east = true; } //西 if(j-1 >= 0 && mazeNodes[i][j-1].getValue() == 0){ mazeNodes[i][j].way_west = true; } //南 if(i+1 < row && mazeNodes[i+1][j].getValue() == 0){ mazeNodes[i][j].way_south = true; } //北 if(i-1>= 0 && mazeNodes[i-1][j].getValue() == 0){ mazeNodes[i][j].way_north = true; } } } } } public void goMaze(){ //将入口压栈 if(mazeNodes[0][0].getValue() == 0){ myStack.push(mazeNodes[0][0]); } while(!myStack.isEmpty()){ //栈不为空返回栈顶元素 mazeNode = myStack.peek(); int x = mazeNode.getX(); int y = mazeNode.getY(); //栈顶元素若为出口，则跳出 while() if(mazeNode.getX() == row-1 && mazeNode.getY() == colum-1) { break; } //向西走 if(mazeNode.way_west == true){ //将当前节点的西节点压入栈 myStack.push(mazeNodes[x][y-1]); //封当前节点向西的路 mazeNodes[x][y].way_west = false; //封返回当前节点的路 mazeNodes[x][y-1].way_east = false; continue; } //向东走 else if(mazeNode.way_east == true){ //将当前节点的东节点压入栈 myStack.push(mazeNodes[x][y+1]); //封当前节点向东的路 mazeNodes[x][y].way_east = false; //封返回当前节点的路 mazeNodes[x][y+1].way_west = false; continue; } //向南走 else if(mazeNode.way_south == true){ //将当前节点的南节点压入栈 myStack.push(mazeNodes[x+1][y]); //封当前节点向南的路 mazeNodes[x][y].way_south = false; //封返回当前节点的路 mazeNodes[x+1][y].way_north = false; continue; } //向北走 else if(mazeNode.way_north == true){ //将当前节点的北节点压入栈 myStack.push(mazeNodes[x-1][y]); //封当前节点向北的路 mazeNodes[x][y].way_north = false; //封返回当前节点的路 mazeNodes[x-1][y].way_south = false; continue; } //该节点无路可走 出栈 myStack.pop(); } } //打印路径 public void show(){ //栈为空 迷宫无路径 if (myStack.isEmpty()) { System.out.println("此迷宫无路径~"); return; } //将栈中的路径标记 while (!myStack.isEmpty()) { mazeNode = myStack.peek(); mazeNode.setValue(8); myStack.pop(); } System.out.println("迷宫路径为："); for (int i = 0; i < row; i++) { for (int j = 0; j < colum; j++) { System.out.print(mazeNodes[i][j].getValue() + " "); } System.out.println(); } } }

4.栈

public class MyStack { private MazeNode[] array; private static int size; private static final int INITSIZE = 100; //初始化栈 public MyStack(){ array = new MazeNode[INITSIZE]; } //扩容 private void ensureCapacity(){ if(size == array.length){ Arrays.copyOf(array,array.length+(array.length>>1)); } } //判断栈空不空 public boolean isEmpty(){ return this.size == 0; } //压栈 public void push(MazeNode mazeNode){ ensureCapacity(); array[size] = mazeNode; size++; } //出栈 public void pop(){ if(isEmpty()){ return; } size--; } //返回栈顶元素 public MazeNode peek(){ if(size == 0){ throw new EmptyStackException(); } return array[size-1]; } }