如何利用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; } }
總結
到此這篇關於如何利用JAVA實現走迷宮程序的文章就介紹到這瞭,更多相關JAVA走迷宮程序內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!