迷宫——搜索迷宫最短路径

目录：

1.定义常量 2.定义节点信息 3.定义链式队列 4.定义迷宫类 5.测试代码

1.定义常量

public interface Constant { int RIGHT = 0; //右方向 int DOWN = 1; //下方向 int LEFT = 2; //左方向 int UP = 3; }

2.定义节点类型

/** * 定义迷宫节点类型 */ private static class MazeNoe{ //节点的值 int val; //节点的坐标 int x; int y; //节点的四个行走状态，true表示可以走，flase表示不能走 boolean[] state; /** * 迷宫路径的初始化 */ public MazeNoe(int data, int i, int j) { this.state = new boolean[4]; this.val = data; this.x = i; this.y = j; } }

3.定义链式队列

package maze; /* * 链式队列 * front：指向的是链表的头节点 * rear: 永远指向的是末尾节点 * @param <T> */ public class LinkQueue<T>{ private Entry<T> front;// 指向头节点(队头) private Entry<T> rear; // 指向尾节点(队尾) private int count;// 记录队列节点的个数 /** * 初始化，front和rear都指向头节点 */ public LinkQueue(){ this.front = this.rear = new Entry<>(null, null); } /** * 入队操作 * @param val */ public void offer(T val){ Entry<T> node = new Entry<>(val, null); this.rear.next = node; this.rear = node; this.count++; } /** * 出队操作 * @return */ public T poll(){ T val = null; if(this.front.next != null){ val = this.front.next.data; this.front.next = this.front.next.next; // 删除队列最后一个元素，要把rear指向front，队列才能判空 if(this.front.next == null){ this.rear = this.front; } this.count--; } return val; } public T peek(){ T val = null; if(this.front.next != null){ val = this.front.next.data; } return val; } /** * 判断队列空 * @return */ public boolean isEmpty(){ return this.front == this.rear; } /** * 返回队列元素的个数 * @return */ public int size(){ return this.count; } /** * 节点类型定义 * @param <T> */ static class Entry<T>{ T data; Entry<T> next; public Entry(T data, Entry<T> next) { this.data = data; this.next = next; } } }

4.定义迷宫类

public class Maze { //迷宫的所有路径存储在二维数组中 private MazeNoe[][] maze; //迷宫路径节点的队列结构，采用层层扩张的方式，寻找迷宫最优的路径信息 private LinkQueue<MazeNoe> queue; //迷宫的行数 private int row; //迷宫的列数 private int col; //记录迷宫节点的行走路径 private MazeNoe[] pathrecord; /** * 迷宫初始化 */ public Maze(int row, int col) { this.row = row; this.col = col; this.maze = new MazeNoe[row][col]; this.queue = new LinkQueue<>(); this.pathrecord = new MazeNoe[row*col]; } /** * 初始化指定位置的迷宫节点 */ public void initMazeNode(int data,int i,int j){ this.maze[i][j] = new MazeNoe(data,i,j); } /** * 修改迷宫所有节点四个方向的行走状态信息 */ public void initMazeNodePathState(){ for (int i=0;i<row;i++){ for (int j=0;j<col;j++){ if (this.maze[i][j].val==1){ //值为1 的节点的方向不用调整 因为走不到 continue; } if (j<col-1 && this.maze[i][j+1].val==0){ this.maze[i][j].state[Constant.RIGHT] = true; } if (i<row-1 && this.maze[i+1][j].val==0){ this.maze[i][j].state[Constant.DOWN] = true; } if (j>0 &&this.maze[i][j-1].val==0){ this.maze[i][j].state[Constant.LEFT] = true; } if (i>0 && this.maze[i-1][j].val==0){ this.maze[i][j].state[Constant.UP] = true; } } } } /** * 寻找迷宫路径 */ public void findMazePath(){ if (maze[0][0].val==1){ return; } queue.offer(maze[0][0]); while (!queue.isEmpty()){ MazeNoe top = queue.peek(); int x = top.x; int y = top.y; //往右方向走 if (maze[x][y].state[Constant.RIGHT]) { maze[x][y].state[Constant.RIGHT] =false; maze[x][y+1].state[Constant.LEFT] =false; queue.offer(maze[x][y+1]); pathrecord[x*col+y+1]=maze[x][y]; if (check(x,y+1)){ //判断是否找到了右下角出口节点，找到的话，直接退出 return; } } //往左方向走 if (maze[x][y].state[Constant.LEFT]){ maze[x][y].state[Constant.LEFT] = false; maze[x][y-1].state[Constant.RIGHT] = false; queue.offer(maze[x][y-1]); pathrecord[x*col+y-1] = maze[x][y]; if (check(x,y-1)){ //判断是否找到了右下角出口节点，找到的话，直接退出 return; } } //往上方向走 if (maze[x][y].state[Constant.UP]){ maze[x][y].state[Constant.UP] = false; maze[x-1][y].state[Constant.DOWN] = false; queue.offer(maze[x-1][y]); pathrecord[(x-1)*col+y] = maze[x][y]; if (check(x-1,y)){ //判断是否找到了右下角出口节点，找到的话，直接退出 return; } } //向下方向走 if (maze[x][y].state[Constant.DOWN]){ maze[x][y].state[Constant.DOWN] = false; maze[x+1][y].state[Constant.UP] = false; queue.offer(maze[x+1][y]); pathrecord[(x+1)*col+y] = maze[x][y]; if (check(x+1,y)){ //判断是否找到了右下角出口节点，找到的话，直接退出 return; } } queue.poll(); } } /** * 检查是否找到右下角出口的节点 * @param x * @param y * @return */ private boolean check(int x, int y) { return x==this.row-1 && y==this.col-1; } /** * 打印迷宫路径搜索的结果 */ public void showMazePath() { if(pathrecord[row*col-1] == null){ System.out.println("迷宫不存在有效路径"); } else { System.out.println("迷宫路径如下"); int x = row-1; int y = col-1; for(;;){ maze[x][y].val = '*'; MazeNoe node = pathrecord[x*col+y]; if(node == null){ break; } x = node.x; y = node.y; } for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if(maze[i][j].val == '*'){ System.out.print('*' + " "); } else { System.out.print(maze[i][j].val + " "); } } System.out.println(); } } }

5.测试代码

public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.println("请输入迷宫的行列数："); int row,col,data; row = in.nextInt(); col = in.nextInt(); Maze maze = new Maze(row,col); System.out.println("请输入迷宫的路径"); for (int i=0;i<row;i++){ for (int j=0;j<col;j++){ data = in.nextInt(); maze.initMazeNode(data,i,j); } } //修改迷宫所有节点四个方向的行走状态信息 maze.initMazeNodePathState(); //寻找迷宫路径 maze.findMazePath(); //打印迷宫路径搜索的结果 maze.showMazePath(); }