递归之迷宫回溯问题【数据结构及算法】

public class MiGong {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//先创建一个二维数组，模拟迷宫
		//地图
		int[][] map=new int[8][7];
		//使用1表示障碍物
		//先用1，构成一个封闭空间
		for(int i=0;i<8;i++) {
			map[i][0]=1;
			map[i][6]=1;
		}
		for(int i=0;i<7;i++) {
			map[0][i]=1;
			map[7][i]=1;
		}
		
		//封闭空间内设置障碍物
		map[3][1]=1;
		map[3][2]=1;
		
		//使用递归回溯给小球找路
		setWay(map,1,1);
		
		//输出新的地图，小球走过，并标识过的递归
		System.out.println("小球走过，并标识过的地图的情况");
		for(int i=0;i<7;i++) {
			for(int j=0;j<6;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}	
		
		//使用递归回溯来给小球找路
		//说明
		//1.map 表示地图
		//2.i，j表示从地图的哪个位置出发（1，1）
		//3.如果小球能够到达map[6][5],说明通路找到
		//4.约定：当map[i][j]为0时表示该点没有走过 ；当为1时，表示障碍物；当为2时，表示通路可以走；当为3时，该点走过但不通。
		//5.走迷宫的策略为下→右→上→左，如果走不通，则回溯
		
		//return 如果找到通路，返回true。否则返回false
		
		public static boolean setWay(int[][] map,int i,int j) {
			if(map[6][5]==2) {
				return true;
			}else {
				if(map[i][j]==0) {          //说明此点还没有走过
					map[i][j]=2;//假定此点可以走通
					if(setWay(map,i+1,j)) {        //xia
						return true;
					}else if(setWay(map,i,j+1)) {    //you
						return true;
					}else if(setWay(map,i-1,j)) {     //shang
						return true;
					}else if(setWay(map,i,j-1)) {
						return true;
					}else {
						//说明该点不通，死路
						map[i][j]=3;
						return false;
					}
				}else {        //如果map[i][j]!=0,可能是1，2，3
					return false;
					}
				}
		}
}