package com.xcc.dataStructures.demo05_recursion;

/**
 * 迷宫
 *
 * @author xiaocheng
 * @date 2020/12/1 10:39
 */
public class MiGong {

    public static void main(String[] args) {
        int[][] arr = init(8, 7);
        arr[3][1] = 1;
        arr[3][2] = 1;
        arr[1][2] = 1;
        arr[2][2] = 1;
        show(arr);
//        getWay(arr, 1, 1);
        getWay1(arr, 1, 1);
        System.out.println("==============================");
        show(arr);
    }

    //右下左上
    public static boolean getWay1(int[][] arr, int i, int j) {
        if (arr[6][5] == 2) {
            return true;
        } else {
            if (arr[i][j] == 0) { //这条路还没有走过
                //设置这条路为可以走
                arr[i][j] = 2;
                if (getWay1(arr, i, j + 1)) { //右边这条路是通路
                    return true;
                } else if (getWay1(arr, i + 1, j)) { //下面这条路是通路
                    return true;
                } else if (getWay1(arr, i, j - 1)) { //左边这条路是通路
                    return true;
                } else if (getWay1(arr, i - 1, j)) { //上这条路是通路
                    return true;
                } else {
                    arr[i][j] = 3;
                    return false;//否则就是没有通路
                }
            } else { //如果(arr[i][j]为 1 , 3 则返回false此路不通
                return false;
            }
        }
    }

    //下右上左
    //约定： 当 map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 ； 2 表示通路可以走 ； 3 表示该点已经 走过，但是走不通
    public static boolean getWay(int[][] arr, int i, int j) {
        if (arr[6][5] == 2) {
            return true;
        } else {
            if (arr[i][j] == 0) { //这条路没走过
                //假设这条路可以走通
                arr[i][j] = 2;
                if (getWay(arr, i + 1, j)) {//下
                    return true;
                } else if (getWay(arr, i, j + 1)) {//右
                    return true;
                } else if (getWay(arr, i - 1, j)) {//上
                    return true;
                } else if (getWay(arr, i, j - 1)) {//左
                    return true;
                } else {
                    arr[i][j] = 3;
                    return false;
                }
            } else { //如果 map[i][j] != 0 , 可能是 1， 3
                return false;
            }
        }

    }

    /**
     * 遍历数组
     */
    private static void show(int[][] arr) {
        for (int[] ints : arr) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();
        }
    }

    /**
     * 初始化数组
     *
     * @param h 高
     * @param w 宽
     */
    private static int[][] init(int h, int w) {
        int[][] arr = new int[h][w];
        for (int i = 0; i < w; i++) {
            arr[0][i] = 1;
            arr[h - 1][i] = 1;
        }
        for (int i = 0; i < h; i++) {
            arr[i][0] = 1;
            arr[i][w - 1] = 1;
        }
        return arr;
    }

}