public class Recursion {
​
    public static void main(String[] args) {
        recursion(2);
    }
​
    public static void recursion(int n){
        if (n > 0){//当n>0继续递归前进
            recursion(n-1);
        }
        //当n<0时，则停止递归前进，开始递归返回
        System.out.println(n);
    }
}

public class Labyrinth2 {

    // 用于保存最短路径，需为全局变量
    static List<Position> shortest = new ArrayList<>();

    public static void main(String[] args) {
        //创建一个7x7的迷宫，1为墙壁，0为通道，2为起点, 有俩个终点map[6,2],map[6,5]
        int map[][] = {
                {1, 1, 1, 1, 1, 1, 1},
                {2, 0, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 1, 0, 0, 0, 0, 1},
                {1, 0, 0, 0, 1, 1, 1},
                {1, 0, 0, 0, 0, 0, 1},
                {1, 1, 0, 1, 1, 0, 1}
        };

        printMap(map);
        Position position = new Position(1, 0);
        Stack<Position> path = new Stack<>();

        findWay(map, position, path);
        System.out.println("迷宫通过路径为：");
        printMap(map);
        System.out.printf("最短路径是：");
        for (Position pos : shortest){
            System.out.printf("[%d, %d] ",pos.row, pos.cul);
        }
    }

    //判断下一步是否是可行的通道
    public static boolean isClear(int[][] map, Position cur, Position next){
        //判断下一步坐标是否超出迷宫限制
        if (next.row>=0 && next.row<map.length && next.cul>=0 && next.cul<map[next.row].length){
            //判断下一步通道是否为0，即可行通道，或下一步的值是否大于当前位置的值，即是之前路径走过的通道但非回头路
            if (map[next.row][next.cul] == 0 || map[cur.row][cur.cul] < map[next.row][next.cul]){
                return true;
            }
        }
        return false;
    }

    /**
     * 迷宫的定义：
     *  0为通道，1为墙壁，2为起点，终点在迷宫的最下方的通道，即map.length-1
     * 寻找最短路径思路：
     *  1.先假定该通道是可行路径上的一点，压入存放可行路径的栈path
     *  2.判断是否已到达终点cur.row == map.length-1，如果已经到达终点，则判断path和shortest内的路径哪个短，
     *    如果path内的路径短，则把path的值覆盖掉shortest的值
     *  3.往四方探路：
     *    1)因为是要寻找最短路径，所以得把所有通道路径走一遍，即每次都要往四方(下-右-上-左)可行的通道都出发，
     *      所以不用if-else if语句，只使用if语句来判断通道是否可行（条件为：isClear方法返回的boolean值）
     *    2)当当前方向是可行的通道时，要为该方向对应的下个通道赋值为(现在所处位置的值+1)，来防止走回头路(在isClear中有判断是否为回头路的条件)
     *    3)当 1)和2) 执行完后，再来递归(返回到流程1)，同样使用if语句，条件为递归方法findWay，
     *      当当前方向的通道有可行的路径时(即该次递归方法最终返回的值为true)，就返回true
     *  4.如果四方都不可行，就说明当前所在位置的通道是死路，把它弹出可行路径栈path，
     *    返回false归回到上次递归方法，如果该递归方法为第一个递归方法则结束返回结果回到main方法
     * @param map 迷宫地图
     * @param cur 当前位置在迷宫中所处的坐标
     * @param path 储存离开迷宫路径的每个通道坐标
     * @return
     */
    public static boolean findWay(int[][] map, Position cur, Stack<Position> path){
        path.push(cur);
        if (cur.row == map.length-1){
            if (path.size() < shortest.size() || shortest.isEmpty()){
                shortest = (List<Position>)path.clone();
            }
        }

        //向下走
        Position next = new Position(cur.row, cur.cul);
        next.row = cur.row+1;
        if (isClear(map, cur, next)){ //判断next坐标是否是可行的通道
            map[next.row][next.cul] = map[cur.row][cur.cul]+1;//将cur坐标的值+1赋给next坐标
            if (findWay(map, next, path)) { //如果条件内的递归方法最终返回ture,则表示next的通道是可行路径上的一点
                return true;
            }
        }

        //向右走
        next = new Position(cur.row, cur.cul);
        next.cul = cur.cul+1;
        if (isClear(map, cur, next)){
            map[next.row][next.cul] = map[cur.row][cur.cul]+1;
            if (findWay(map, next, path)) {
                return true;
            }
        }

        //向上走
        next = new Position(cur.row, cur.cul);
        next.row = cur.row-1;
        if (isClear(map, cur, next)){
            map[next.row][next.cul] = map[cur.row][cur.cul]+1;
            if (findWay(map, next, path)) {
                return true;
            }
        }

        //向左走
        next = new Position(cur.row, cur.cul);
        next.cul = cur.cul - 1;
        if (isClear(map, cur, next)){
            map[next.row][next.cul] =map[cur.row][cur.cul]+1;
            if (findWay(map, next, path)) {
                return true;
            }
        }

        path.pop();//所在坐标的通道四方都不是可行路径上的一点，即该通道也不是可行路径上的一点，弹出可行路径栈
        return false;//返回false，归回到上次递归方法，如已归回到第一次的递归方法，则返回结果到main方法
    }

    public static void printMap(int[][] map){
        for (int[] i : map){
            for (int item : i){
                System.out.printf("%d\t", item);
            }
            System.out.println();
        }
    }
}

//用于储存位置在迷宫地图中的坐标
class Position{
     public int row;
     public int cul;

    public Position() {
    }

    public Position(int row, int cul) {
        this.row = row;
        this.cul = cul;
    }

    @Override
    public String toString() {
        return "Position{" +
                "row=" + row +
                ", cul=" + cul +
                '}';
    }
}

public class Queen8 {

    static int max = 8;
    static int count = 0;//计算共有多少摆放的方式
    //储存8个皇后摆放的位置，下标是棋盘行，值是棋盘列: int[row]=cul, row对应棋盘的行, cul对应棋盘的列
    static int[] array = new int[max];

    public static void main(String[] args) {

        Queen8 queen8 = new Queen8();
        queen8.putQueen(0);

        System.out.printf("共有 %d 种摆放方式\n", count);//92种
    }

    /**
     * 摆放皇后
     * @param row 皇后所在的行
     */
    public void putQueen(int row){
        //因为棋盘只有8行，所有当行数等于8(数组是从0开始), 则说明8个皇后已摆放完成
        if (row == max){
            print();
            return;
        }

        for (int cul=0; cul<max; cul++){//遍历该行的每一列
            //因为cul值是否根据循环变化的，所以只要没有符合游戏规则，就会重新赋值给array[row]
            array[row] = cul;//先假定row行的cul位置符合规则
            if (judge(row)){//判断该位置是否符合规则
                putQueen(row+1);//符合则递进到下一行
            }
            //不符合则继续循环到下一列
        }
    }

    /**
     * 判断皇后的摆放是否符号游戏规则
     * 皇后摆放的规则：
     *  不能在同一行：因为是用一维数组来对应皇后的坐标，棋盘的行对应数组的下标，
     *                每一行只有一个皇后，所以不用考虑同一行的问题
     *  不能在同一列：因为是用一维数组array来储存皇后所在的列，所在只要array内没有相同的值就说明没有皇后在同一列
     *  不能再同一斜线：当要和[row,cul]同一斜线时，只要[row-1,cul+1] 或[row-1,cul-1],
     *                可以看出 |row-(row-1)| = |cul-(cul+1)| = |cul-(cul-1)| = 1,
     *                即俩个位置的行和列相减后的差的绝对值都相等，所以只要该差的绝对值不相等就不在同一条斜线
     * @param row 皇后所在的行
     * @return
     */
    public static boolean judge(int row){
        for (int i=0; i<row; i++){ //遍历在row行前的所有皇后
            //判断是否在同一列 array[i] == array[row]
            //判断是否在同一斜线 Math.abs(row-i) == Math.abs(array[row]-array[i])
            if (array[i] == array[row] || Math.abs(row-i) == Math.abs(array[row]-array[i])){
                return false; //如果在同一列或同一斜线，则不符合游戏规则，返回false
            }
        }
        return true;
    }

    //打印棋盘内皇后的摆放位置，根据行排序，如第一个数是第一行皇后所在的列
    public static void print(){
        count++;
        for (int i : array){
            System.out.print(i+" ");
        }
        System.out.println();
    }
}