如何利用JAVA实现走迷宫程序

本Demo使用三个类

一个Test类

一个自定义的Stack类

一个自定义的Queue类

可以实现的功能：

1.对于一个写在文本文件中的迷宫，能够将其转换为二维数组用广度优先搜索实现查找最短路径

2.可以不定义迷宫的入口和出口，能自动查找到出入口

前提是要有一个对应路径的.txt文件

这里举个例子吧,我的是"F:/1号迷宫(0,18).txt"路径下

运行结果

示例代码

注释写的很详细，这里就不多赘述了

package com;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;

/**迷宫测试
* 1号迷宫(0,18).txt
*2号迷宫(0,1).txt
*/
public class Test {
   public static void main(String[] args) throws Exception {
       Test test = new Test();
       //通过文件输入流得到二维数组
       char[][] arr = test.getFile("F:/1号迷宫(0,18).txt");
       System.out.println("二维数组的长度为:"+arr[0].length);
       int deep = test.getDeepByChar(arr);
       System.out.println("二维数组的深度为:"+deep);

//找到入口位置
       int [] begin = test.begin(arr);
       System.out.println("入口位置:("+begin[0]+","+begin[1]+")");
       //找到出口位置
       int [] end = test.end(arr,deep);
       System.out.println("出口位置:("+end[0]+","+end[1]+")");
       System.out.println("=================================打印二维数组============================================");
       //打印二维数组
       test.printArr(arr,deep);
       System.out.println("=================================最短路径图展示===========================================");
       //求最短路径图
       int[][] bfs = test.bfs(arr,begin,end,deep);
       for (int i = 0; i < deep; i++) {
           for (int j = 0; j < bfs[0].length; j++) {
               System.out.print(bfs[i][j]+"\t");
           }
           System.out.println();
       }
       System.out.println("================================最短路径===============================================");
       //根据最短路径图得到最短路径
       int[][] result = test.getLoaderFromMap(bfs, begin, end, deep);
       //得到result的深度
       int deep1 = test.getDeepByInt(result);
       for (int i = 0; i < deep1; i++) {
           System.out.println("("+result[i][0]+","+result[i][1]+")\t");
       }
   }

//求最短路径图
   public int[][] bfs(char [][] arr, int [] begin, int [] end,int deep) {
       //移动的四个方向
       int[] dx = {1, 0, -1, 0};
       int[] dy = {0, 1, 0, -1};
       //d二维数组用来表示路径图
       int[][] d = new int [deep][arr[0].length];
       //储存未进行处理的节点,这里LinkedList实现了Deque,Deque又继承了Queue
       Queue1<int[]> que = new Queue1<>();
//        Queue<int []> que = new LinkedList<>();
       //将所有的位置都初始化为最大
       for(int i = 0; i < d.length; i++) {
           for(int j = 0; j < d[0].length; j++) {
               d[i][j] = -1;
           }
       }
       //将起始点放入队列
       que.offer(begin);
       //将起始点最短路径设为0
       d[begin[0]][begin[1]] = 0;
       //一直循环直到队列为空
       while(!que.isEmpty()) {
           //取出队列中最前端的点
           int [] current = que.poll();
           //如果是终点则结束
           if(current[0] == end[0] && current[1] == end[1]){
               break;
           }
           //四个方向循环
           for(int i = 0; i < 4; i++) {
               //试探
               int nx = current[0] + dx[i];
               int ny = current[1] + dy[i];
               //判断是否可以走
               if(nx >= 0 && nx < deep && ny >= 0 && ny < d[0].length  && arr[nx][ny] == '0' && d[nx][ny] == -1) {
                   //如果可以走，则将该点的距离加1
                   d[nx][ny] = d[current[0]][current[1]] + 1;
                   //并将该点放入队列等待下次处理
                   int[] c = {nx, ny};
                   que.offer(c);
               }
           }
       }
       return d;
   }

//根据最短路径图得到最短路径
   private int [][] getLoaderFromMap(int [][] map,int [] begin,int [] end,int deep) {
       int k = 0;//标志位
       //创建二维数组最终正序存储结果
       int[][] resultList = new int[map.length * map.length][2];
       //result数组存储每个正确位置的下标
       int[] result;
       //创建一个栈,从出口开始把位置压入栈，之后再遍历栈就是正的迷宫顺序
       Stack1<int[]> stack = new Stack1<>();
       //先把出口压入栈
       stack.push(end);
       //移动的四个方向
       int[] dx = {1, 0, -1, 0};
       int[] dy = {0, 1, 0, -1};
       //已知出口和入口,从出口逆推入口
       //只要出口没有和入口下标重合，就一直循环
       while(true){
           //获得栈中最顶层元素，不取出
           int[] current = stack.peek();
           for (int i = 0; i < 4; i++) {
               //试探
               int nx = current[0] + dx[i];
               int ny = current[1] + dy[i];
               //如果当前节点不是入口节点，就继续向前追溯
               if(map[current[0]][current[1]] != map[begin[0]][begin[1]]){
                   //判断是否可以走
                   if (nx >= 0 && nx < deep && ny >= 0 && ny < map[0].length && map[nx][ny] != -1) {
                       //从后往前追溯，前一个数值一定比后一个小1
                       if(map[nx][ny] == map[current[0]][current[1]]-1){
                           //如果可以走,将此节点入栈
                           result = new int[]{nx, ny};
                           stack.push(result);
                       }
                   }
               }else{
                   k++;
                   break;
               }
           }
           //k是为了打破最外层循环，在比较map[current[0]][current[1]] != map[begin[0]][begin[1]]时
           //如果当前节点等于入口时，就应该打破循环，但是while和for是两重循环，所以加一个标志位再打破一次
           if(k != 0){
               break;
           }
       }

//取出栈中元素赋给resultList
       int len = stack.length();
       for(int i = 0;i < len;i++){
           result = stack.pop();
           resultList[i][0] = result[0];
           resultList[i][1] = result[1];
       }
       return resultList;
   }

//把文件中的二进制转换为二维数组
   private char[][] getFile (String pathName) throws Exception {
       File file = new File(pathName);
       //文件不存在时抛出异常
       if (!file.exists())
           throw new RuntimeException("Not File!");
       //字符缓冲输入流//缓冲流是处理流，要先new一个字符输入流
       BufferedReader br = new BufferedReader(new FileReader(file));
       //字符串str用来存储一行数据
       String str;
       //初始化一个二维数组
       char[][] arr = new char[110][];
       //x用来记录读取的行数
       int x = 0;
       while ((str = br.readLine()) != null) {
           x++;
           //把字符串变成字符数组存储
           char[] cArr = str.toCharArray();
           //把一行字符数组加入到二维数组中
           arr[x - 1] = cArr;
       }
       br.close();
       return arr;
   }

//找到入口位置
   private int[] begin ( char[][] arr){
       //存储起点的下标begin[0]=x,begin[1]=y
       int[] begin = new int[2];
       //用StringBuffer把数组转为字符串，方便找到其中的元素
       StringBuffer s = new StringBuffer();
       for (int i = 0; i < arr[0].length; i++) {
           s.append(arr[0][i]);
       }
       //如果入口在第一行
       //判断下标是否存在
       if (s.indexOf("0") != -1) {
           begin[0] = 0;
           begin[1] = s.indexOf("0");
           return begin;
       } else {
           //如果入口在第一列
           for (int i = 0; i < arr.length; i++) {
               if (arr[i][0] == '0') {
                   begin[0] = i;
                   begin[1] = 0;
                   return begin;
               }
           }
       }
       return begin;
   }

//找到出口位置
   private int[] end ( char[][] arr, int deep){
       //存储出口的下标end[0]=x,end[1]=y
       int[] end = new int[2];
       //出口在最后一列上     //18是第二个表的深度
       for (int i = 0; i < deep; i++) {
           //最后一列上找到出口
           if (arr[i][arr[0].length - 1] == '0') {
               end[0] = i;
               end[1] = arr[0].length - 1;
               return end;
           }
       }
       //出口在最后一行上
       for (int i = 0; i < arr.length; i++) {
           //最后一行上找到出口    //deep为最后一行的下标
           if (arr[deep - 1][i] == '0') {
               end[0] = deep - 1;
               end[1] = i;
               return end;
           }
       }
       return end;
   }

/**
    * 由于二维数组刚创建时的默认行数为110，但是实际存储不到110，在对二维数组进行遍历得到实际有效深度时
    * 就会抛出数组下标越界异常，发生越界异常可认为到达二维数组的深度边缘，此时的深度就是有效深度
    * 将异常捕获，返回此时深度就可以得到二维数组的有效深度
    */
   //得到二维数组有效深度
   private int getDeepByChar ( char[][] arr){
       int y = 0;//深度
       for (int i = 0; i < arr.length; i++) {
           //由于i可能越界，当i越界时就认为到达最底部,返回当前y值
           try {
               //如果第一列那行数据不为1或0，就认为此行无效
               if (arr[i][0] != '1' && arr[i][0] != '0') {
                   break;
               }
           } catch (Exception e) {
               return y;
           }
           y++;
       }
       return y;
   }

//得到二维整形数组有效深度
   private int getDeepByInt ( int[][] arr){
       int y = 0;//深度
       for (int i = 0; i < arr.length; i++) {
           //如果遇到(0,0)的，认为已经失效
           if (arr[i][0] == 0 && arr[i][1] == 0) {
               break;
           }
           y++;
       }
       return y;
   }

//打印二维数组
   private void printArr ( char[][] arr, int deep){
       for (int i = 0; i < arr[0].length; i++) {
           for (int j = 0; j < deep; j++) {
               try {
                   System.out.print(arr[i][j] + "\t");
               } catch (Exception e) {
               }
           }
           System.out.println();
       }
   }
}

/**
* 队列
* @param <E>
*/
class Queue1<E> {
   private E[] arr;//使用数组表示一个队列
   private int size;//size表示队列中有效元素个数
   private int putIndex=-1;//putIndex表示从队列中放数的索引始终从队首取，并且取得索引始终为arr[0]

//有参构造
   protected Queue1(int initSize){
       if(initSize < 0){
           throw new IllegalArgumentException("参数错误");
       }
       arr = (E[])new Object[initSize];
       size = 0;
   }
   //无参构造，默认10个长度大小
   protected Queue1(){
       this(110);
   }

//入队
   protected void offer(E e){
       if(size == arr.length) {
           throw new ArrayIndexOutOfBoundsException("无法进行push操作，队列已满");
       }
       arr[++putIndex] = e;
       size++;
   }

//判断队列是否为空
   protected boolean isEmpty(){
       return size == 0?true:false;
   }

//出队
   protected E poll() {
       if (size == 0) {
           throw new ArrayIndexOutOfBoundsException("This queue is empty!当前队列为空");
       }
       E tmp = arr[0];
       //后面的元素向前移动
       for (int i = 0; i < size - 1; i++) {
           arr[i] = arr[i + 1];
       }
       arr[size - 1] = null;
       putIndex--;
       size--;
       return tmp;
   }
}

/**
* 栈
* @param <E>
*/
class Stack1<E> {
   private int maxSize;//最大长度
   private int top = -1;//栈顶指针，初始指向-1
   private E[] data;//数组代替栈存放元素

//初始化栈大小
   protected Stack1(int maxSize){
       if(maxSize > 0){
           this.maxSize = maxSize;
           //data数组对象也要初始化大小
           data = (E[])new Object[maxSize];
       }else{
           throw new IllegalArgumentException("初始化栈大小失败，参数不合法");
       }
   }

//默认初始化大小为10
   protected Stack1(){
       //调用有参构造，传入10
       this(10);
   }

//入栈
   protected boolean push(E e){
       //先判断栈是否已满
       if(top == maxSize-1){
           //扩容
           this.resize();
       }
       //先top++,再top = e
       data [++top] = e;
       return true;
   }

//判断栈是否为空
   protected boolean isEmpty(){
       return top == -1;
   }

//得到栈的长度
   protected int length(){
       return top+1;
   }
   //出栈
   protected E pop(){
       //先判断栈是否为空
       if(top == -1){
           throw new IllegalArgumentException("栈当前为空");
       }
       else{
           E e = data[top];
           //先top = null,再top--
           data[top--] = null;
           return  e;
       }
   }

//查看栈顶元素
   protected E peek(){
       //先判断栈是否为空
       if(top == -1){
           throw new IllegalArgumentException("栈当前为空");
       }else{
           return data[top];
       }
   }

//栈扩容，默认扩容为原来的一倍
   protected void resize(){
       int newSize = maxSize*2;
       E[] newData = (E[])new Object[newSize];
       for (int i = 0;i < data.length;i ++){
           newData[i] = data[i];
       }
       //刷新最大长度
       maxSize = newSize;
       //再把newData赋值给data数组
       data = newData;
   }
}

总结

来源：https://blog.csdn.net/suo_jia_hao/article/details/118253958