迷宫问题

迷宫问题

整体问题

判断从起点能否走到终点，如果可以打印出来路径

思路

1.创建迷宫
2.设置起点和终点
3.如果走到终点退出递归
4.如果这个点没走过，假设它可以走通，递归的对它的四个方向走，如果通就返回true，四个方向都不通就返回false
5.如果这个点走过，就不能再走，直接返回false

优化策略

1.小球找到的路径与程序员设置的策略有关
2.可以将各种不同的策略共4乘3乘2乘1种策略依次走一遍，求最短

代码

package recursion;

public class Maze {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//创建数组
		//级别
		int [][] map=new int[8][7];
		//上下全部的置为1
		for(int i=0;i<7;i++) {
			map[0][i]=1;
			map[7][i]=1;
			
		}
		
		//左右都置为1
		for(int i=0;i<8;i++) {
			map[i][0]=1;
			map[i][6]=1;
		}
		
		//设置挡板
		map[3][1]=1;
		map[3][2]=1;
		
		//输出地图
		System.out.println("地图的情况:");
		for(int i=0;i<8;i++) {
			for(int j=0;j<7;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		//使用递归回溯给小球找路
		boolean flag=setWay(map, 1, 1);
		System.out.println(flag);
		//输出新的地图，这个地图中就有小球走过的路
		//标识过的地图，有通路就是2，没有通路就是3
		for(int i=0;i<8;i++) {
			for(int j=0;j<7;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		
	}
	
	//使用递归函数来给小球找路
	//map表示对应的矩阵
	//i,j表示从哪个位置开始找
	//表示如果找到通路的话，就返回true，否则就返回false
	//如果小球可以到map[6][5]位置，就说明通路已经找到，
	//约定，当地图的(i,j)为0的时候，表示没有走过，1表示墙，2是通路,3是之前走过但是没有走通
	//策略方法;下->右->上->左,如果走不通再结束
	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)) {//向下走
					return true;
				}else if(setWay(map, i, j+1)) {//向右走
					return true;
				}else if(setWay(map, i-1, j)) {//向上走
					return true;
				}else if(setWay(map, i, j-1)){//向左走
					return true;
				}else {//死路
					//说明该点是走不通的
					map[i][j]=3;
					return false;
				}
			}else {//可能是1，2，或者3
				return false;
			}
		}
	
	}
	

}