package cn.iocoder.yudao.framework.common.thealgorithms.backtracking;

//public final class MazeRecursion {
//    private MazeRecursion() {
//    }
//
//    public static void mazeRecursion() {
//        // First create a 2 dimensions array to mimic a maze map
//        int[][] map = new int[8][7];
//        int[][] map2 = new int[8][7];
//
//        // We use 1 to indicate wall
//        // Set the ceiling and floor to 1
//        for (int i = 0; i < 7; i++) {
//            map[0][i] = 1;
//            map[7][i] = 1;
//        }
//
//        // Then we set the left and right wall to 1
//        for (int i = 0; i < 8; i++) {
//            map[i][0] = 1;
//            map[i][6] = 1;
//        }
//
//        // Now we have created a maze with its wall initialized
//
//        // Here we set the obstacle
//        map[3][1] = 1;
//        map[3][2] = 1;
//
//        // Print the current map
//        System.out.println("The condition of the map： ");
//        for (int i = 0; i < 8; i++) {
//            for (int j = 0; j < 7; j++) {
//                System.out.print(map[i][j] + " ");
//            }
//            System.out.println();
//        }
//
//        // clone another map for setWay2 method
//        for (int i = 0; i < map.length; i++) {
//            System.arraycopy(map[i], 0, map2[i], 0, map[i].length);
//        }
//
//        // By using recursive backtracking to let your ball(target) find its way in the
//        // maze
//        // The first parameter is the map
//        // Second parameter is x coordinate of your target
//        // Third parameter is the y coordinate of your target
//        setWay(map, 1, 1);
//        setWay2(map2, 1, 1);
//
//        // Print out the new map1, with the ball footprint
//        System.out.println("After the ball goes through the map1，show the current map1 condition");
//        for (int i = 0; i < 8; i++) {
//            for (int j = 0; j < 7; j++) {
//                System.out.print(map[i][j] + " ");
//            }
//            System.out.println();
//        }
//
//        // Print out the new map2, with the ball footprint
//        System.out.println("After the ball goes through the map2，show the current map2 condition");
//        for (int i = 0; i < 8; i++) {
//            for (int j = 0; j < 7; j++) {
//                System.out.print(map2[i][j] + " ");
//            }
//            System.out.println();
//        }
//    }
//
//    /**
//     * Using recursive path finding to help the ball find its way in the maze
//     * Description：
//     * 1. map (means the maze)
//     * 2. i, j (means the initial coordinate of the ball in the maze)
//     * 3. if the ball can reach the end of maze, that is position of map[6][5],
//     * means the we have found a path for the ball
//     * 4. Additional Information： 0 in the map[i][j] means the ball has not gone
//     * through this position, 1 means the wall, 2 means the path is feasible, 3
//     * means the ball has gone through the path but this path is dead end
//     * 5. We will need strategy for the ball to pass through the maze for example:
//     * Down -> Right -> Up -> Left, if the path doesn't work, then backtrack
//     *
//     * @author OngLipWei
//     * @version Jun 23, 2021 11:36:14 AM
//     * @param map The maze
//     * @param i   x coordinate of your ball(target)
//     * @param j   y coordinate of your ball(target)
//     * @return If we did find a path for the ball，return true，else false
//     */
//    public static boolean setWay(int[][] map, int i, int j) {
//        if (map[6][5] == 2) { // means the ball find its path, ending condition
//            return true;
//        }
//        if (map[i][j] == 0) { // if the ball haven't gone through this point
//            // then the ball follows the move strategy : down -> right -> up -> left
//            map[i][j] = 2; // we assume that this path is feasible first, set the current point to 2
//                           // first。
//            if (setWay(map, i + 1, j)) { // go down
//                return true;
//            } else if (setWay(map, i, j + 1)) { // go right
//                return true;
//            } else if (setWay(map, i - 1, j)) { // go up
//                return true;
//            } else if (setWay(map, i, j - 1)) { // go left
//                return true;
//            } else {
//                // means that the current point is the dead end, the ball cannot proceed, set
//                // the current point to 3 and return false, the backtracking will start, it will
//                // go to the previous step and check for feasible path again
//                map[i][j] = 3;
//                return false;
//            }
//        } else { // if the map[i][j] != 0 , it will probably be 1,2,3, return false because the
//            // ball cannot hit the wall, cannot go to the path that has gone though before,
//            // and cannot head to deadened.
//            return false;
//        }
//    }
//
//    // Here is another move strategy for the ball: up->right->down->left
//    public static boolean setWay2(int[][] map, int i, int j) {
//        if (map[6][5] == 2) { // means the ball find its path, ending condition
//            return true;
//        }
//        if (map[i][j] == 0) { // if the ball haven't gone through this point
//            // then the ball follows the move strategy : up->right->down->left
//            map[i][j] = 2; // we assume that this path is feasible first, set the current point to 2
//                           // first。
//            if (setWay2(map, i - 1, j)) { // go up
//                return true;
//            } else if (setWay2(map, i, j + 1)) { // go right
//                return true;
//            } else if (setWay2(map, i + 1, j)) { // go down
//                return true;
//            } else if (setWay2(map, i, j - 1)) { // go left
//                return true;
//            } else {
//                // means that the current point is the dead end, the ball cannot proceed, set
//                // the current point to 3 and return false, the backtracking will start, it will
//                // go to the previous step and check for feasible path again
//                map[i][j] = 3;
//                return false;
//            }
//        } else { // if the map[i][j] != 0 , it will probably be 1,2,3, return false because the
//            // ball cannot hit the wall, cannot go to the path that has gone through before,
//            // and cannot head to deadend.
//            return false;
//        }
//    }
//}


public final class MazeRecursion {

    private MazeRecursion() {
    }

    // 使用递归解决迷宫问题
    public static void mazeRecursion() {
        // 首先创建一个二维数组来模拟迷宫地图
        int[][] map = new int[8][7];
        int[][] map2 = new int[8][7];

        // 使用1表示墙壁
        // 设置顶部和底部为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }

        // 然后设置左右墙壁为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        // 现在我们已经创建了一个初始化墙壁的迷宫

        // 这里我们设置障碍物
        map[3][1] = 1;
        map[3][2] = 1;

        // 打印当前地图的状态
        System.out.println("地图的当前状态：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

        // 克隆另一个地图用于setWay2方法
        for (int i = 0; i < map.length; i++) {
            System.arraycopy(map[i], 0, map2[i], 0, map[i].length);
        }

        // 使用递归回溯让你的球（目标）在迷宫中找到出路
        // 第一个参数是地图
        // 第二个参数是目标的x坐标
        // 第三个参数是目标的y坐标
        setWay(map, 1, 1);
        setWay2(map2, 1, 1);

        // 打印新的map1，显示球的足迹
        System.out.println("球穿过map1后，显示当前map1的状态");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

        // 打印新的map2，显示球的足迹
        System.out.println("球穿过map2后，显示当前map2的状态");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map2[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 使用递归寻路帮助球在迷宫中找到出路
     * 描述：
     * 1. map（表示迷宫）
     * 2. i, j（表示球在迷宫中的初始坐标）
     * 3. 如果球能到达迷宫的终点，即map[6][5]的位置，
     * 表示我们为球找到了一条路径
     * 4. 额外信息：map[i][j]中的0表示球还没有经过这个位置，1表示墙壁，2表示路径可行，3
     * 表示球已经经过这条路径但这条路径是死路
     * 5. 我们需要为球通过迷宫制定策略，例如：
     * 下 -> 右 -> 上 -> 左，如果路径不通，则回溯
     *
     * @param map 迷宫
     * @param i   球的x坐标
     * @param j   球的y坐标
     * @return 如果我们为球找到了一条路径，返回true，否则返回false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) { // 表示球找到了路径，结束条件
            return true;
        }
        if (map[i][j] == 0) { // 如果球还没有经过这个点
            // 球按照移动策略：下 -> 右 -> 上 -> 左
            map[i][j] = 2; // 我们先假设这条路径是可行的，将当前点设置为2。
            if (setWay(map, i + 1, j)) { // 向下走
                return true;
            } else if (setWay(map, i, j + 1)) { // 向右走
                return true;
            } else if (setWay(map, i - 1, j)) { // 向上走
                return true;
            } else if (setWay(map, i, j - 1)) { // 向左走
                return true;
            } else {
                // 表示当前点是死路，球无法继续前进，将当前点设置为3并返回false，
                // 开始回溯，它将返回到上一步并再次检查可行路径
                map[i][j] = 3;
                return false;
            }
        } else { // 如果map[i][j] != 0，可能是1,2,3，返回false因为
            // 球不能撞墙，不能走已经走过的路径，
            // 也不能走向死路。
            return false;
        }
    }

    // 这里是另一个球的移动策略：上->右->下->左
    public static boolean setWay2(int[][] map, int i, int j) {
        if (map[6][5] == 2) { // 表示球找到了路径，结束条件
            return true;
        }
        if (map[i][j] == 0) { // 如果球还没有经过这个点
            // 球按照移动策略：上->右->下->左
            map[i][j] = 2; // 我们先假设这条路径是可行的，将当前点设置为2。
            if (setWay2(map, i - 1, j)) { // 向上走
                return true;
            } else if (setWay2(map, i, j + 1)) { // 向右走
                return true;
            } else if (setWay2(map, i + 1, j)) { // 向下走
                return true;
            } else if (setWay2(map, i, j - 1)) { // 向左走
                return true;
            } else {
                // 表示当前点是死路，球无法继续前进，将当前点设置为3并返回false，
                // 开始回溯，它将返回到上一步并再次检查可行路径
                map[i][j] = 3;
                return false;
            }
        } else { // 如果map[i][j] != 0，可能是1,2,3，返回false因为
            // 球不能撞墙，不能走已经走过的路径，
            // 也不能走向死路。
            return false;
        }
    }
}
