如何利用JAVA实现走迷宫程序如何利用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又继承了QueueQueue1 que = new Queue1<>(); //Queue 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); //将起始点最短路径设为0d[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) {//如果可以走，则将该点的距离加1d[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 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) {//从后往前追溯，前一个数值一定比后一个小1if(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; }}//取出栈中元素赋给resultListint 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]=yint[] 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]=yint[] 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 */class Queue1 {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 */class Stack1 {private int maxSize; //最大长度private int top = -1; //栈顶指针，初始指向-1private E[] data; //数组代替栈存放元素//初始化栈大小protected Stack1(int maxSize){if(maxSize > 0){this.maxSize = maxSize; //data数组对象也要初始化大小data = https://www.it610.com/article/(E[])new Object[maxSize]; }else{throw new IllegalArgumentException("初始化栈大小失败，参数不合法"); }}//默认初始化大小为10protected Stack1(){//调用有参构造，传入10this(10); }//入栈protected boolean push(E e){//先判断栈是否已满if(top == maxSize-1){//扩容this.resize(); }//先top++,再top = edata [++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; returne; }}//查看栈顶元素protected E peek(){//先判断栈是否为空if(top == -1){throw new IllegalArgumentException("栈当前为空"); }else{return data[top]; }}//栈扩容，默认扩容为原来的一倍protected void resize(){int newSize = maxSize*2; E[] newData = https://www.it610.com/article/(E[])new Object[newSize]; for (int i = 0; i < data.length; i ++){newData[i] = data[i]; }//刷新最大长度maxSize = newSize; //再把newData赋值给data数组data = newData; }}

总结
【如何利用JAVA实现走迷宫程序】到此这篇关于如何利用JAVA实现走迷宫程序的文章就介绍到这了,更多相关JAVA走迷宫程序内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！