如何利用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!

推薦閱讀: