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ā)生越界異?？烧J(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;
    }
}