迷宫问题 - 球寻找出口（经典递归问题）

迷宫问题–小球找出口(经典递归问题)

递归的经典案例----小球找路
说明：小球得到的路径,和程序设置的找路策略有关：如小球行走的顺序依次为(上下左右,或者上左下右)其路径都不相同

            迷宫问题-----小球找路思路分析

① 使用二维数组模拟地图,小球从(1，1)出发;
② 如果小球在数组的右下角,即(6,5)位置,表示小球找到的路游戏通关;
③ 约定：当数组元素为:
0 的时候,表示这是路径,且没有走过
1的时候表示墙，
2表示通路可走;
3表示该路已经走过了,且时死路;

约定迷宫中的小球按照,上下左右的方式寻找路径;
如果找不到,就回溯,并将死路其标志为3；
找到了返回true,找不到就返回false

public static boolean setWay(int[][] map,int i,int j) {//传入数组；从map[i][j]开始
		
		System.out.println("");
		for(int i1=0;i1<map.length;++i1) {
			for(int j1=0;j1<map[0].length;++j1){
			    System.out.print(map[i1][j1]+"  ");
			}
			System.out.println(" ");
		}
		
		if(map[8][8] == 2) {
			return true;
			
			如果迷宫出口已被标记为2；证明小球走过了，那么找到出口,
			然后返回true使所有的递归方法(由于多次调用setWay方法,在栈中有好多setWay方法,每个都相互独立)
			的四个if中的某一个条件成立,进入if执行if中的return;依次下去,直到程序结束;
			
		}
		else {
			if(map[i][j] == 0) {
			
如果数组元素为0,则证明可以走;那么就开始按照走路策略开始走(上下左右)

				map[i][j] = 2;
				
假设,我们当前的路是通的,为什么要这样,因为我们需要将我们走过的路标记为2；
如果该路走不通,那就回溯（又或者小球一步也没有走直接不需要回溯,因为就没有归
直接将当前标志为3，这种情况就是小球被墙包围）,将其标志为3;

 				if(setWay(map,i-1,j)) {//上
					return true;
					
这里返回为true意思为;如果小球找到了出口,开始进行回溯;从map[8][8] == 2开始,
一直返回true，然后进入if,还是返回true,连锁反应,直到回溯到main方法程序
<<但是经过我的测试,发现如果这里的if里面全改为false,程序依然照常运行,所以我认为这里的return 只是起到了结束当前方法的作用,
一直结束到main方法,程序结束>>

 				}
				else if(setWay(map,i+1,j)) {//下
					return true;
				}
				else if(setWay(map,i,j-1)) {//左
					return true;
				}
				else if(setWay(map,i,j+1)) {//右
					return true;
				}
				else {
				
如果四个if都不满足,意思是上下左右都走不通了,小球走进了死路,开始回溯并将该位置标志为3；
证明在这按照该走路策略,是行不通的

					map[i][j] = 3;
					return false;
					
开始回溯,返回false,让所有的if不成立只到退回到某个if成立的位置然后继续按照策略(上下左右)继续行走

				}
			}
			else {
			
如果该路不是0 ，那么就可能为 1 ， 2 ，3 ；证明要么为墙（1）不可以走;
要么为死路(3)走不通;要么为已经走过的路(2);那直接返回false;让四个if不成立进而
直接执行最后一个else,使该位置标志为3;

				return false;				
			}
		}
	}