利用java中的方法递归调用，解决迷宫问题

总体思路

1、利用二维数组表示迷宫

2、设计找路的方法?

关键点

1、知道什么条件表示找到路，退出

2、将每个点的类型，进行规定

3、每个点走路的策略进行制定

//递归调用应用实例-迷宫问题
//小球得到的路径，和程序员设置的找路策略有关即
//找路的上下左右的顺序相关再得到小球路径时，可以先使用(下右上左)再改成(上右下左)，
//看看路径是不是有变化测试回溯现象
//4、扩展思考: 如何求出最短路径
//
//迷宫8行7列
public class hsp221{
	public static void main(String args[]){
		//思路
		//1、先创建迷宫，用二维数组表示int map[][] = new int[8][7]
		//2、先规定map数组中的元素值：0表示可以走，1表示障碍物
		int map[][] = new int[8][7];
		for(int i = 0;i<map.length;i++){
			for(int j = 0; j<map[i].length;j++){
				//将第一行第一列最后一行最后一列，全部设置为1
				if(i == 0 || i == 7 || j==0 || j==6){
					map[i][j] = 1;
				}else{
					map[i][j] = 0;
				}
			}
		}
		//单独设置障碍物
		map[3][1] = 1;
		map[3][2] = 1;
		//再多设置几个障碍物彻底堵死，看看会发生什么
		// map[2][1] = 1;
		// map[2][2] = 1;
		// map[1][2] = 1;
        System.out.println("=========当前地图情况========");
		for(int i = 0;i<map.length;i++){
			for(int j = 0; j<map[i].length;j++){				
	            System.out.print(map[i][j] + "\t");
			}
			System.out.println();
		}


		//3、使用findway来找路
		T t1 = new T();
		t1.findway(map, 1,1);

		//因为数组是引用传递，所以在findway中修改map，main栈中的map也会改变
		System.out.println("========找路情况=========");
		for(int i = 0;i<map.length;i++){
			for(int j = 0; j<map[i].length;j++){
	            System.out.print(map[i][j] + "\t");
			}
			System.out.println();
		}

	}
}


class T{
	//使用递归回溯的思想来解决
	//1、findway专门找出迷宫的路径
	//2、有没有出迷宫返回一个布尔值
	//3、map[][]就是迷宫，i,j代表当前老鼠的位置
	//4、老鼠初始位置为(1，1)     走到(6，5)代表走出迷宫
	//5、因为是递归找路，所以先规定map数组的各个值的含义
	//   0表示可以走，1表示障碍物，2表示可以走，3表示走过但是走不通的路
	//6、当(6，5)表示为2时，则说明找到路，退出
	//7、确定探路策略:先往哪边走，我们规定下->右->上->左
	public boolean findway(int map[][], int i,int j){
        if (map[6][5] == 2) {//说明已经找到路
        	return true;
        }else{
            if(map[i][j] == 0){//说明可以走并且没走过
            	//假定可以走通,如果再下一步没有走通，说明假定错误，需要对其重新赋值
            	map[i][j] = 2;
            	//使用找路策略测试，来确定该位置是否真的可以走通
            	//7、确定探路策略:先往哪边走，我们规定下->右->上->左
            	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{//上下左右都走不通，说明一开始的假定错误
                   map[i][j] = 3;
                   return false;
            	}

            }else{//map[i][j] = 1,2,3 
            	//map[i][j] = 1说明或者3好理解都说明不能走，故返回false
            	//map[i][j] = 2说明来过又回来了，所以还是走不通，返回flase
            	return false;
            }
        }
	}
    


    //修改找路策略进行测试
    public boolean findway1(int map[][], int i,int j){
        if (map[6][5] == 2) {//说明已经找到路
        	return true;
        }else{
            if(map[i][j] == 0){
            	map[i][j] = 2;
            	
            	//下->右->上->左 -> 上->右->下->左
            	if(findway(map, i-1,j)){//先尝试走下面
                   return true;
            	}else if(findway1(map,i,j+1)){//尝试右面
                   return true;
            	}else if(findway1(map,i+1,j)){//尝试上面
                   return true;
            	}else if(findway1(map,i,j-1)){//尝试左面
                   return true;
            	}else{//上下左右都走不通，说明一开始的假定错误
                   map[i][j] = 3;
                   return false;
            	}

            }else{
            	return false;
            }
        }
	}


}

判断一个点能否走通的条件是判断周围4个点能否走通，将一个点能否走通的问题一次分解为判断相邻四个点能否走通?