一个网格迷宫由n行n列的单元格组成，每个大院个要么是空地（用0表示），要么是障碍物（用1表示），你的任务是找一条从起点到终点的移动序列，其中只能上下左右移动到相邻单元格。任何时候都不能在有障碍物的单元格中，也不能走到迷宫之外，起点为左上角和终点右下角。
解决迷宫路径查找问题，寻找一条从左上角迷宫入口到右下角迷宫出口的一条有效路径，0代表可走，1代表能走，找到请输出最终的迷宫和路径信息，找不到请输出不存在有效路径。
1、定义一个迷宫节点类型（MazeNode）的二维数组
2、初始化每个格子中的value值，给二维数组每个格子存放对象。对象的value值只能为0（当前格子可以走）或者1（当前格子不能走）
3、初始化每个格子四个方向（东西南北）是否是可走状态（0可走，1不可走）
4、开始走迷宫。采用栈操作，记录行走的路径，将左上角元素入栈，判断当前栈顶元素的哪个方向可走，将其中一个可走方向进行入栈操作，知道右下角元素停止。栈中保存走过的路径。注意：如果遇到走入死胡同问题，此时需要将是栈顶元素并且栈顶元素的四个方向都不能行走，此时将其出栈，选择新方向再次入栈，直到右下角元素停止。
迷宫的结点类：
package cc;
public class MazeNode {
private int value;//迷宫节点数据0或者1
private int i;//迷宫节点所在的行
private int j;//迷宫节点所在的列
private boolean[] state;//当前节点可走或不可走
/*构造*/
public MazeNode(int value,int i,int j) {
this.value=value;
this.i=i;
this.j=j;
state=new boolean[Constant.SIZE];
}
/*get和set*/
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public int getI() {
return i;
}
public int getJ() {
return j;
}
public void setState(int direction,boolean state) {
this.state[direction]=state;
}
public boolean getState(int direction) {
return state[direction];
}
}
常量的类：
package cc;
public class Constant {
public static final int SIZE=4;//四个方向
public static final int EAST=0;//东
public static final int WEAST=1;//西
public static final int SORTH=2;//南
public static final int NORTH=3;//北
public static final int ABLE=0;//可走
}
迷宫类：
package cc;
import java.util.Scanner;
import java.util.Stack;
/*
* @author : CC
* @data : 2020-12-14
* */
public class Maze {
private MazeNode[][] mazeNodes;//迷宫数组
private int column;//列
private int row;//行
private Stack<MazeNode> stack;//栈
/*构造*/
public Maze(int row,int column) {
this.mazeNodes=new MazeNode[row][column];
this.column=column;
this.row=row;
stack=new Stack<MazeNode>();
}
/*初始化迷宫*/
private void initValue() {
Scanner sc=new Scanner(System.in);
System.out.println("请输入迷宫路径:");
for(int i=0;i<row;i++) {
for(int j=0;j<column;j++) {
this.mazeNodes[i][j]=new MazeNode(sc.nextInt(),i,j);
}
}
sc.close();
}
/*初始化迷宫节点的状态*/
private void initState() {
for(int i=0;i<row;i++) {
for(int j=0;j<column;j++) {
if(mazeNodes[i][j].getValue()==Constant.ABLE) {
//东
if(j+1<column&&mazeNodes[i][j+1].getValue()==Constant.ABLE) {
mazeNodes[i][j].setState(Constant.EAST,true);
}
//南
if(i+1<row&&mazeNodes[i+1][j].getValue()==Constant.ABLE) {
mazeNodes[i][j].setState(Constant.SORTH,true);
}
//西
if(j-1>=0&&mazeNodes[i][j-1].getValue()==Constant.ABLE) {
mazeNodes[i][j].setState(Constant.WEAST,true);
}
//北
if(i-1>=0&&mazeNodes[i-1][j].getValue()==Constant.ABLE) {
mazeNodes[i][j].setState(Constant.NORTH,true);
}
}
}
}
}
/*走迷宫*/
public void goMaze() {
initValue();
initState();
if(mazeNodes[0][0].getValue()!=Constant.ABLE) {
//如果连起点都不能走的话，就表示没有路径
System.out.println("没有迷宫路径!");
return;
}
//起点入栈
stack.push(mazeNodes[0][0]);
//开始走迷宫
while(!stack.isEmpty()) {
MazeNode top=stack.peek();//获取栈顶元素
int i=top.getI();
int j=top.getJ();
if(i==row-1&&j==column-1) {
//找到了终点
System.out.println("找到迷宫路径!");
show();
return;
}
//判断栈顶元素是否是死胡同
if(top.getState(Constant.EAST)==false&&top.getState(Constant.WEAST)==false&&top.getState(Constant.NORTH)==false&&top.getState(Constant.SORTH)==false) {
//如果是，直接出栈
stack.pop();
}
//判断各个位置是否可走
//由于起点在左上角，所以我们从东边开始判断
if(top.getState(Constant.EAST)) {
stack.push(mazeNodes[i][j+1]);//东边入栈
//当前节点的东边false
mazeNodes[i][j].setState(Constant.EAST, false);
//当前节点的东边节点的西边false
mazeNodes[i][j+1].setState(Constant.WEAST, false);
}
//南
if(top.getState(Constant.SORTH)) {
stack.push(mazeNodes[i+1][j]);//南边入栈
mazeNodes[i][j].setState(Constant.SORTH, false);
mazeNodes[i+1][j].setState(Constant.NORTH, false);
}
//西
if(top.getState(Constant.WEAST)) {
stack.push(mazeNodes[i][j-1]);//西边入栈
mazeNodes[i][j].setState(Constant.WEAST, false);
mazeNodes[i][j-1].setState(Constant.EAST, false);
}
//北
if(top.getState(Constant.NORTH)) {
stack.push(mazeNodes[i-1][j]);//北边入栈
mazeNodes[i][j].setState(Constant.NORTH, false);
mazeNodes[i-1][j].setState(Constant.SORTH, false);
}
}
System.out.println("此迷宫无解!");
}
/*输出路径*/
private void show(){
while (!stack.isEmpty()) {
MazeNode top = stack.peek();// 获取栈顶元素
top.setValue(2);
stack.pop();// 出栈操作
}
System.out.println("所找到的路径为值2的坐标：");
for(int i = 0;i<row;i++){
for(int j = 0;j<column;j++){
System.out.print(mazeNodes[i][j].getValue()+" ");
}
System.out.println();
}
}
}
测试类：
package cc;
public class Test {
public static void main(String[] args) {
Maze t1=new Maze(4,5);
t1.goMaze();
}
}
运行截图：
如有不足和建议，欢迎指正和讨论。
