欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

如何利用JAVA實(shí)現(xiàn)走迷宮程序

 更新時(shí)間:2021年06月27日 10:00:37   作者:愚笨難解  
最近經(jīng)常在機(jī)房看同學(xué)在玩一個(gè)走迷宮的游戲,比較有趣,自己也用java實(shí)現(xiàn)了一個(gè),這篇文章主要給大家介紹了關(guān)于如何利用JAVA實(shí)現(xiàn)走迷宮程序的相關(guā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

    這篇文章主要介紹了java如何獲取用戶登錄ip、瀏覽器信息、SessionId,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-11-11
  • Java包裝類的緩存機(jī)制原理實(shí)例詳解

    Java包裝類的緩存機(jī)制原理實(shí)例詳解

    這篇文章主要介紹了Java包裝類的緩存機(jī)制原理實(shí)例詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-12-12
  • Java中的HashMap弱引用之WeakHashMap詳解

    Java中的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-09
  • 淺析12306售票算法(java版)

    淺析12306售票算法(java版)

    這篇文章主要介紹了淺析12306售票算法(java版)的相關(guān)資料,需要的朋友可以參考下
    2016-02-02
  • SpringBoot3集成MyBatis詳解

    SpringBoot3集成MyBatis詳解

    MyBatis是一款開源的持久層框架,它極大地簡(jiǎn)化了與數(shù)據(jù)庫(kù)的交互流程,MyBatis更具靈活性,允許開發(fā)者直接使用SQL語(yǔ)句與數(shù)據(jù)庫(kù)進(jìn)行交互,本文將詳細(xì)介紹在Spring Boot項(xiàng)目中如何集成MyBatis,以實(shí)現(xiàn)對(duì)數(shù)據(jù)庫(kù)的輕松訪問(wèn)和操作,需要的朋友可以參考下
    2023-12-12
  • java自己手動(dòng)控制kafka的offset操作

    java自己手動(dòng)控制kafka的offset操作

    這篇文章主要介紹了java自己手動(dòng)控制kafka的offset操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
    2021-02-02
  • Java實(shí)戰(zhàn)之在線寄查快遞系統(tǒng)的實(shí)現(xiàn)

    Java實(shí)戰(zhàn)之在線寄查快遞系統(tǒng)的實(shí)現(xiàn)

    這篇文章主要介紹了如何利用Java制作一個(gè)在線寄查快遞系統(tǒng),文中采用的技術(shù)有java、SpringBoot、FreeMarker、Mysql,需要的可以參考一下
    2022-02-02
  • G1垃圾回收器在并發(fā)場(chǎng)景調(diào)優(yōu)詳解

    G1垃圾回收器在并發(fā)場(chǎng)景調(diào)優(yōu)詳解

    這篇文章主要為大家介紹了G1垃圾回收器在并發(fā)場(chǎng)景調(diào)優(yōu)詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步早日升職加薪
    2022-04-04
  • Spring中的@RestControllerAdvice注解使用解析

    Spring中的@RestControllerAdvice注解使用解析

    這篇文章主要介紹了Spring中的@RestControllerAdvice注解使用解析,@RestControllerAdvice?是?Spring?框架中一個(gè)用于統(tǒng)一處理控制器異常和返回結(jié)果的注解,它可以被用來(lái)定義全局異常處理程序和全局響應(yīng)結(jié)果處理程序,需要的朋友可以參考下
    2024-01-01
  • springboot如何接收get和post請(qǐng)求參數(shù)

    springboot如何接收get和post請(qǐng)求參數(shù)

    這篇文章主要介紹了springboot如何接收get和post請(qǐng)求參數(shù),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2023-06-06

最新評(píng)論