来搜这个问题的肯定是对这个问题有一定的了解,在这里就简单讲一下什么是迷宫问题. 就是可以用一个二维数组来描绘一个迷宫,其中数字1(或者其他数字都可以,这个无所谓)代表四周的边界和迷宫中的障碍物,这个二维数组类似下图:

图中1表示的部分就是墙和障碍物,0都是可以通行的

现在给定一个起点和终点,来寻找起点到终点之间的路径,例如从arr[1][1]到arr[7][7],就是从左上方到右下方.

经过上面的分析我们发现了一个很重要的问题,就是如果下一个点是障碍物或走不通或者走过了,就应该回到上一个点继续在其他方向寻找,递归可以解决这个问题. 以第一个图的迷宫为例,例如:如果我们从起点arr[1][1]的位置先向下寻找,是走不通的,因为下面是1.

我们先把(1,1)这两个数据作为坐标传递到方法里,首先判断(1,1)所在位置是否为0,显然是为0的可以继续向下走,这里我们自己调用自己,把下一个坐标传进方法,向下走就应该是(2,1),到了这一步发现当前二维数组的这个位置是1,应该退回,那么此时我们就让该方法返回,并且返回false,这样,我们就又退回到了第一个方法中,此时这个方法中的坐标还是(1,1)这个点,开始下一个方法的寻找.

大家都知道,在调用方法时其实是在方法栈中压入了一个新的栈帧,这个栈帧里的变量是独立的和原方法中的变量是两块区域.第一次调用方法时变量是(1,1),第二次调用方法时为(2,1),这只是代表在第二个方法中变量的值为(2,1),上一个方法变量仍为(1,1),当第二次执行的方法结束返回时,方法从方法栈上弹出,此时又回到了调用的位置处,即,回到了第一个方法,方法的变量又会到了(1,1),在使用这个变量进行下一个方向的寻找. 如下图所示: 此上就是实现回溯的机制.