递归 -迷宫问题

迷宫问题

  • 问题描述
  • 递归的原则
  • 问题分析
  • 代码分析

问题描述

用一个二维数组模拟一个迷宫,定义一个入口和出口,找出路径找到通往出口的路径

拓展问题,如何找出最短路径? —待施工……

递归的原则

递归的应用原则

  • 执行一个方法时,就会创建一个新的受保护的栈空间

  • 每个空间的变量都是局部变量(引用传递除外),相互不会影响

  • 递归必须向退出递归的条件逼近,否则会无限递归(死龟)

  • 当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就把结果返回给谁,同时当方法执行完毕或者返回时,该方法就执行完毕

问题分析

  • 迷宫问题,从起点开始,定义一个策略(往四个方向探索的顺序)

  • 定义: 0->表示为探索过的,1->墙, 2->通路(已经走过切,能走通), 3->死路(走过判断为死路)

  • 然后递归的结束条件就是出口点被修改为2,如果不满足这个条件就按照策略开始走

  • 每当开始探索一个点,就假设,这个点为通路,修改为2,究竟是否为通路,要看回溯的结果

  • 如果,一个点上下左右都不能走,就修改为3,表示死路

代码分析

/**
     *
     * @param map 迷宫地图,0表示路,1表示墙,2表示通路,3表示死路
     * @param i 迷宫起点
     * @param j
     */
    public static boolean setMap(int[][] map, int i, int j) {
        if(map[6][6] == 2) {
            return true;
        } else {
            if(map[i][j] == 0) {
                map[i][j] = 2;  //假设这个点可以走通,若果不能会回溯
                if(setMap(map, i+1, j)) { //先向下走
                    return true;
                } else if(setMap(map, i, j+1)) { //向右走
                    return true;
                } else if(setMap(map, i-1, j)) { //向上走
                    return true;
                } else if(setMap(map, i, j-1)) { //向左走
                    return true;
                } else { //上下左右都无法走通
                    map[i][j] = 3;
                    return false;
                }
            } else { //可能是1,2,3墙不能走,2表示走过,3表示不能走,这三种情况都是不能走
                return false;
            }
        }
    }

用一个8*8的迷宫模拟一下,迷宫如下

1 1 1 1 1 1 1 1
1 入口 1 1
1 1
1 1 1 1
1 1 1
1 1
1 出口 1
1 1 1 1 1 1 1 1

执行完毕后

1 1 1 1 1 1 1 1
1 2 1 1
1 2 2 2 2 1
1 1 3 1 2 1
1 1 2 1
1 2 1
1 2 2 2 1
1 1 1 1 1 1 1 1

说明

第二张表,里面的3,就是因为,在坐标(2,2)的点会按照策略先向下走,但是(3,2)点的左,右,下都是墙(1),上面又是通路(2),因此这个向下的调用会返回false,并且标记为死路(3),然后进行策略的下一步,向右