回顾数据结构（Java版）——递归回溯实现迷宫

素颜马尾好姑娘i 2023-06-07 12:21 14阅读 0赞

使用递归回溯实现迷宫，主要的是理解递归的含义，因此先来简单的分析一下递归。概念不多说了，直接上代码调试

package com.wrial.recursion;
    /*
     * @Author  Wrial
     * @Date Created in 10:14 2019/10/13
     * @Description 阶乘
     */
    
    public class Factorial {
    
        public static void main(String[] args) {
            int factorial = new Factorial().factorial(5);
            System.out.println(factorial);
        }
    
        /*
        执行流程：
        先将main，factorial（5放入方法栈），然后将factorial(4)....放入直到return1，然后一次出栈执行
         */
    
        public int factorial(int num) {
            if (num <= 1) {
                System.out.printf("%d\t", num);
                return 1;
            } else {
    
                int temp = factorial(num - 1) * num;
                System.out.printf("%d\t", num);
                return temp;
            }
    
        }
    }

调试输出结果为1 … 可以看出并不是从高到低，在递归执行的时候，每遇到递归函数都会单独开辟一个递归的方法栈，并且压入栈中，直至遇到终止条件然后回退执行，可以在递归程序打一个端点认真体会。

Connected to the target VM, address: '127.0.0.1:54109', transport: 'socket'
    1	2	3	4	5	120
    Disconnected from the target VM, address: '127.0.0.1:54109', transport: 'socket'

迷宫代码

package com.wrial.recursion;
    /*
     * @Author  Wrial
     * @Date Created in 9:38 2019/10/15
     * @Description 递归实现迷宫问题
     */
    
    import javax.imageio.ImageReader;
    
    public class maze {
    
        public static int x = 5;
        public static int y = 5;
    
    
        public static void main(String[] args) {
            //先创建一个二维数组，模拟迷宫//
            int[][] map = 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;
            }
            //设置障碍物,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] + "\t");
                }
                System.out.println();
            }
    
            findWay(map, 1, 1);
            System.out.println("地图的情况");
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 7; j++) {
                    System.out.printf(map[i][j] + "\t");
                }
                System.out.println();
            }
    
        }
        /*
        i和j是起点坐标   x和y是终点坐标
        顺序是上右左下
         */
        public static boolean findWay(int[][] map, int i, int j) {
    
            //递归结束条件
            if (map[x][y] == 2) {
                return true;
            } else {
                //如果可以走
                if (map[i][j] == 0) {
                    //先置为2
                    map[i][j] = 2;
                    if (findWay(map, i + 1, j)) {
                        return true;
                    } else if (findWay(map, i, j + 1)) {
                        return true;
                    } else if (findWay(map, i - 1, j)) {
                        return true;
                    } else if (findWay(map, i, j + 1)) {
                        return true;
                    } else {
                        //上下左右都走不通就重新置为3并返回
                        map[x][y] = 3;
                        return false;
                    }
                } else {
                    //如果为2或者3就返回false
                    return false;
                }
            }
    
        }
    }

地图的情况
    1	1	1	1	1	1	1	
    1	0	0	0	0	0	1	
    1	0	0	0	0	0	1	
    1	1	1	0	0	0	1	
    1	0	0	0	0	0	1	
    1	0	0	0	0	0	1	
    1	0	0	0	0	0	1	
    1	1	1	1	1	1	1	
    地图的情况
    1	1	1	1	1	1	1	
    1	2	0	0	0	0	1	
    1	2	2	2	0	0	1	
    1	1	1	2	0	0	1	
    1	0	0	2	0	0	1	
    1	0	0	2	0	2	1	
    1	0	0	2	2	2	1	
    1	1	1	1	1	1	1

2的路径就是地图路径  
怎么测试回溯？可以适当在在地图中加一些死路。

总的来说递归实现迷宫还是蛮简单的，前提是理解递归。