使用一个队列,采用层层扩张的方式,寻找迷宫最优的路径信息,再用一个迷宫节点数组记录行走信息
方向常量定义:
public interface Constant { // 右方向 int RIGHT = 0; // 下方向 int DOWN = 1; // 左方向 int LEFT = 2; // 上方向 int UP = 3; }
所用到的链式队列定义(jdk自带的队列或集合也可以实现此功能)
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; } } }
源代码
/** * 描述: 定义迷宫节点类型 */ private static class MazeNode { // 节点的值 int val; // 节点的x和y坐标 int x; int y; // 节点四个方向的行走状态,true表示可以走,false表示不能走 boolean[] state; /** * 迷宫路径初始化 * @param data * @param i * @param j */ public MazeNode(int data, int i, int j){ this.state = new boolean[4]; this.val = data; this.x = i; this.y = j; } } 源代码 /** * 描述: 迷宫的类型定义 * * @Author shilei * @Date 2019/5/18 */ public class Maze { // 迷宫所有的路径存储在二维数组当中 private MazeNode[][] maze; // 存储迷宫路径节点的队列结构,采用层层扩张的方式,寻找迷宫最优的路径信息 private LinkQueue<MazeNode> queue; // 记录迷宫路径节点的行走信息 private MazeNode[] pathrecord; // 迷宫的行数 private int row; // 迷宫的列数 private int col; /** * 迷宫初始化 * @param row * @param col */ public Maze(int row, int col) { this.row = row; this.col = col; this.maze = new MazeNode[row][col]; this.queue=new LinkQueue<>(); this.pathrecord = new MazeNode[row*col]; } /** * 初始化指定位置的迷宫节点 * @param data * @param i * @param j */ public void initMazeNode(int data, int i, int j) { this.maze[i][j] = new MazeNode(data, i, j); } /** * 修改迷宫所有节点四个方向的行走状态信息 */ public void initMazeNodePathState() { for (int i=0;i<row;i++){ for (int j=0;j<col;j++){ if(j+1<col&&maze[i][j+1].val==0){ maze[i][j].state[Constant.RIGHT]=true; } if(i+1<row&&maze[i+1][j].val==0){ maze[i][j].state[Constant.DOWN]=true; } if(j>0&&maze[i][j-1].val==0){ maze[i][j].state[Constant.LEFT]=true; } if(i>0&&maze[i-1][j].val==0){ maze[i][j].state[Constant.UP]=true; } } } } /** * 寻找迷宫路径 */ public void findMazePath() { if (maze[0][0].val != 0) { return; } queue.offer(maze[0][0]); while(!queue.isEmpty()){ MazeNode top = queue.peek(); int x = top.x; int y = top.y; if(x == row-1 && y == col-1){ return; } // 往右方向走 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(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(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(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]; } queue.poll(); } } /** * 打印迷宫路径搜索的结果 */ public void showMazePath(){ if(pathrecord[row*col-1] == null){ System.out.println("迷宫不存在有效路径"); } else { int x = row-1; int y = col-1; for(;;){ maze[x][y].val = '*'; MazeNode 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(); } } } /** * 描述: 定义迷宫节点类型 */ private static class MazeNode { // 节点的值 int val; // 节点的x和y坐标 int x; int y; // 节点四个方向的行走状态,true表示可以走,false表示不能走 boolean[] state; /** * 迷宫路径初始化 * @param data * @param i * @param j */ public MazeNode(int data, int i, int j){ this.state = new boolean[4]; this.val = data; this.x = i; this.y = j; } } }View Code
测试类
public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("请输入迷宫的行列数:"); 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(); } }
结果:
请输入迷宫的行列数:4 5 请输入迷宫路径 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 * 1 0 0 0 * * 0 1 0 1 * 1 1 0 0 * * * *