如何利用JAVA實(shí)現(xiàn)走迷宮程序
本Demo使用三個(gè)類
一個(gè)Test類
一個(gè)自定義的Stack類
一個(gè)自定義的Queue類
可以實(shí)現(xiàn)的功能:
1.對(duì)于一個(gè)寫在文本文件中的迷宮,能夠?qū)⑵滢D(zhuǎn)換為二維數(shù)組用廣度優(yōu)先搜索實(shí)現(xiàn)查找最短路徑
2.可以不定義迷宮的入口和出口,能自動(dòng)查找到出入口
前提是要有一個(gè)對(duì)應(yīng)路徑的.txt文件
這里舉個(gè)例子吧,我的是"F:/1號(hào)迷宮(0,18).txt"路徑下
運(yùn)行結(jié)果
示例代碼
注釋寫的很詳細(xì),這里就不多贅述了
package com; import java.io.BufferedReader; import java.io.File; import java.io.FileReader; /**迷宮測(cè)試 * 1號(hào)迷宮(0,18).txt *2號(hào)迷宮(0,1).txt */ public class Test { public static void main(String[] args) throws Exception { Test test = new Test(); //通過(guò)文件輸入流得到二維數(shù)組 char[][] arr = test.getFile("F:/1號(hào)迷宮(0,18).txt"); System.out.println("二維數(shù)組的長(zhǎng)度為:"+arr[0].length); int deep = test.getDeepByChar(arr); System.out.println("二維數(shù)組的深度為:"+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("=================================打印二維數(shù)組============================================"); //打印二維數(shù)組 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("================================最短路徑==============================================="); //根據(jù)最短路徑圖得到最短路徑 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) { //移動(dòng)的四個(gè)方向 int[] dx = {1, 0, -1, 0}; int[] dy = {0, 1, 0, -1}; //d二維數(shù)組用來(lái)表示路徑圖 int[][] d = new int [deep][arr[0].length]; //儲(chǔ)存未進(jìn)行處理的節(jié)點(diǎn),這里L(fēng)inkedList實(shí)現(xiàn)了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; } } //將起始點(diǎn)放入隊(duì)列 que.offer(begin); //將起始點(diǎn)最短路徑設(shè)為0 d[begin[0]][begin[1]] = 0; //一直循環(huán)直到隊(duì)列為空 while(!que.isEmpty()) { //取出隊(duì)列中最前端的點(diǎn) int [] current = que.poll(); //如果是終點(diǎn)則結(jié)束 if(current[0] == end[0] && current[1] == end[1]){ break; } //四個(gè)方向循環(huán) 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) { //如果可以走,則將該點(diǎn)的距離加1 d[nx][ny] = d[current[0]][current[1]] + 1; //并將該點(diǎn)放入隊(duì)列等待下次處理 int[] c = {nx, ny}; que.offer(c); } } } return d; } //根據(jù)最短路徑圖得到最短路徑 private int [][] getLoaderFromMap(int [][] map,int [] begin,int [] end,int deep) { int k = 0;//標(biāo)志位 //創(chuàng)建二維數(shù)組最終正序存儲(chǔ)結(jié)果 int[][] resultList = new int[map.length * map.length][2]; //result數(shù)組存儲(chǔ)每個(gè)正確位置的下標(biāo) int[] result; //創(chuàng)建一個(gè)棧,從出口開始把位置壓入棧,之后再遍歷棧就是正的迷宮順序 Stack1<int[]> stack = new Stack1<>(); //先把出口壓入棧 stack.push(end); //移動(dòng)的四個(gè)方向 int[] dx = {1, 0, -1, 0}; int[] dy = {0, 1, 0, -1}; //已知出口和入口,從出口逆推入口 //只要出口沒(méi)有和入口下標(biāo)重合,就一直循環(huán) 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]; //如果當(dāng)前節(jié)點(diǎn)不是入口節(jié)點(diǎn),就繼續(xù)向前追溯 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) { //從后往前追溯,前一個(gè)數(shù)值一定比后一個(gè)小1 if(map[nx][ny] == map[current[0]][current[1]]-1){ //如果可以走,將此節(jié)點(diǎn)入棧 result = new int[]{nx, ny}; stack.push(result); } } }else{ k++; break; } } //k是為了打破最外層循環(huán),在比較map[current[0]][current[1]] != map[begin[0]][begin[1]]時(shí) //如果當(dāng)前節(jié)點(diǎn)等于入口時(shí),就應(yīng)該打破循環(huán),但是while和for是兩重循環(huán),所以加一個(gè)標(biāo)志位再打破一次 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; } //把文件中的二進(jìn)制轉(zhuǎn)換為二維數(shù)組 private char[][] getFile (String pathName) throws Exception { File file = new File(pathName); //文件不存在時(shí)拋出異常 if (!file.exists()) throw new RuntimeException("Not File!"); //字符緩沖輸入流//緩沖流是處理流,要先new一個(gè)字符輸入流 BufferedReader br = new BufferedReader(new FileReader(file)); //字符串str用來(lái)存儲(chǔ)一行數(shù)據(jù) String str; //初始化一個(gè)二維數(shù)組 char[][] arr = new char[110][]; //x用來(lái)記錄讀取的行數(shù) int x = 0; while ((str = br.readLine()) != null) { x++; //把字符串變成字符數(shù)組存儲(chǔ) char[] cArr = str.toCharArray(); //把一行字符數(shù)組加入到二維數(shù)組中 arr[x - 1] = cArr; } br.close(); return arr; } //找到入口位置 private int[] begin ( char[][] arr){ //存儲(chǔ)起點(diǎn)的下標(biāo)begin[0]=x,begin[1]=y int[] begin = new int[2]; //用StringBuffer把數(shù)組轉(zhuǎn)為字符串,方便找到其中的元素 StringBuffer s = new StringBuffer(); for (int i = 0; i < arr[0].length; i++) { s.append(arr[0][i]); } //如果入口在第一行 //判斷下標(biāo)是否存在 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){ //存儲(chǔ)出口的下標(biāo)end[0]=x,end[1]=y int[] end = new int[2]; //出口在最后一列上 //18是第二個(gè)表的深度 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為最后一行的下標(biāo) if (arr[deep - 1][i] == '0') { end[0] = deep - 1; end[1] = i; return end; } } return end; } /** * 由于二維數(shù)組剛創(chuàng)建時(shí)的默認(rèn)行數(shù)為110,但是實(shí)際存儲(chǔ)不到110,在對(duì)二維數(shù)組進(jìn)行遍歷得到實(shí)際有效深度時(shí) * 就會(huì)拋出數(shù)組下標(biāo)越界異常,發(fā)生越界異常可認(rèn)為到達(dá)二維數(shù)組的深度邊緣,此時(shí)的深度就是有效深度 * 將異常捕獲,返回此時(shí)深度就可以得到二維數(shù)組的有效深度 */ //得到二維數(shù)組有效深度 private int getDeepByChar ( char[][] arr){ int y = 0;//深度 for (int i = 0; i < arr.length; i++) { //由于i可能越界,當(dāng)i越界時(shí)就認(rèn)為到達(dá)最底部,返回當(dāng)前y值 try { //如果第一列那行數(shù)據(jù)不為1或0,就認(rèn)為此行無(wú)效 if (arr[i][0] != '1' && arr[i][0] != '0') { break; } } catch (Exception e) { return y; } y++; } return y; } //得到二維整形數(shù)組有效深度 private int getDeepByInt ( int[][] arr){ int y = 0;//深度 for (int i = 0; i < arr.length; i++) { //如果遇到(0,0)的,認(rèn)為已經(jīng)失效 if (arr[i][0] == 0 && arr[i][1] == 0) { break; } y++; } return y; } //打印二維數(shù)組 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(); } } } /** * 隊(duì)列 * @param <E> */ class Queue1<E> { private E[] arr;//使用數(shù)組表示一個(gè)隊(duì)列 private int size;//size表示隊(duì)列中有效元素個(gè)數(shù) private int putIndex=-1;//putIndex表示從隊(duì)列中放數(shù)的索引始終從隊(duì)首取,并且取得索引始終為arr[0] //有參構(gòu)造 protected Queue1(int initSize){ if(initSize < 0){ throw new IllegalArgumentException("參數(shù)錯(cuò)誤"); } arr = (E[])new Object[initSize]; size = 0; } //無(wú)參構(gòu)造,默認(rèn)10個(gè)長(zhǎng)度大小 protected Queue1(){ this(110); } //入隊(duì) protected void offer(E e){ if(size == arr.length) { throw new ArrayIndexOutOfBoundsException("無(wú)法進(jìn)行push操作,隊(duì)列已滿"); } arr[++putIndex] = e; size++; } //判斷隊(duì)列是否為空 protected boolean isEmpty(){ return size == 0?true:false; } //出隊(duì) protected E poll() { if (size == 0) { throw new ArrayIndexOutOfBoundsException("This queue is empty!當(dāng)前隊(duì)列為空"); } E tmp = arr[0]; //后面的元素向前移動(dòng) 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;//最大長(zhǎng)度 private int top = -1;//棧頂指針,初始指向-1 private E[] data;//數(shù)組代替棧存放元素 //初始化棧大小 protected Stack1(int maxSize){ if(maxSize > 0){ this.maxSize = maxSize; //data數(shù)組對(duì)象也要初始化大小 data = (E[])new Object[maxSize]; }else{ throw new IllegalArgumentException("初始化棧大小失敗,參數(shù)不合法"); } } //默認(rèn)初始化大小為10 protected Stack1(){ //調(diào)用有參構(gòu)造,傳入10 this(10); } //入棧 protected boolean push(E e){ //先判斷棧是否已滿 if(top == maxSize-1){ //擴(kuò)容 this.resize(); } //先top++,再top = e data [++top] = e; return true; } //判斷棧是否為空 protected boolean isEmpty(){ return top == -1; } //得到棧的長(zhǎng)度 protected int length(){ return top+1; } //出棧 protected E pop(){ //先判斷棧是否為空 if(top == -1){ throw new IllegalArgumentException("棧當(dāng)前為空"); } else{ E e = data[top]; //先top = null,再top-- data[top--] = null; return e; } } //查看棧頂元素 protected E peek(){ //先判斷棧是否為空 if(top == -1){ throw new IllegalArgumentException("棧當(dāng)前為空"); }else{ return data[top]; } } //棧擴(kuò)容,默認(rèn)擴(kuò)容為原來(lái)的一倍 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]; } //刷新最大長(zhǎng)度 maxSize = newSize; //再把newData賦值給data數(shù)組 data = newData; } }
總結(jié)
到此這篇關(guān)于如何利用JAVA實(shí)現(xiàn)走迷宮程序的文章就介紹到這了,更多相關(guān)JAVA走迷宮程序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java如何獲取用戶登錄ip、瀏覽器信息、SessionId
這篇文章主要介紹了java如何獲取用戶登錄ip、瀏覽器信息、SessionId,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-11-11Java中的HashMap弱引用之WeakHashMap詳解
這篇文章主要介紹了Java中的HashMap弱引用之WeakHashMap詳解,當(dāng)內(nèi)存空間不足,Java虛擬機(jī)寧愿拋出OutOfMemoryError錯(cuò)誤,使程序異常終止,也不會(huì)靠隨意回收具有強(qiáng)引用的對(duì)象來(lái)解決內(nèi)存不足的問(wèn)題,需要的朋友可以參考下2023-09-09java自己手動(dòng)控制kafka的offset操作
這篇文章主要介紹了java自己手動(dòng)控制kafka的offset操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2021-02-02Java實(shí)戰(zhàn)之在線寄查快遞系統(tǒng)的實(shí)現(xiàn)
這篇文章主要介紹了如何利用Java制作一個(gè)在線寄查快遞系統(tǒng),文中采用的技術(shù)有java、SpringBoot、FreeMarker、Mysql,需要的可以參考一下2022-02-02G1垃圾回收器在并發(fā)場(chǎng)景調(diào)優(yōu)詳解
這篇文章主要為大家介紹了G1垃圾回收器在并發(fā)場(chǎng)景調(diào)優(yōu)詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步早日升職加薪2022-04-04Spring中的@RestControllerAdvice注解使用解析
這篇文章主要介紹了Spring中的@RestControllerAdvice注解使用解析,@RestControllerAdvice?是?Spring?框架中一個(gè)用于統(tǒng)一處理控制器異常和返回結(jié)果的注解,它可以被用來(lái)定義全局異常處理程序和全局響應(yīng)結(jié)果處理程序,需要的朋友可以參考下2024-01-01springboot如何接收get和post請(qǐng)求參數(shù)
這篇文章主要介紹了springboot如何接收get和post請(qǐng)求參數(shù),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-06-06