迷宫问题

迷宫找路径问题被广泛应用到生活中。比如游戏，玩过LOL的会发现右下角的地图，其实它就是一个典型的找路径问题。

下面用递归+回溯来说一下，如何找到这条路径。

需求

需求如下图所示，有一个9x9的迷宫，从入口走到出口，如何确定一个有效路径？

思路

1.利用二维数组建立好地图的映射，问题就变成了，从[1，1]走到[8，8]

2.假定：0没走过 1墙 2可以走 3走不通

3.走路遵循 下->右->上->左，即先走下，下走不通走右，右走不通走上，上走不通走左

代码

public class Maze { 
	private static int HIGH_MAX=10;
	private static int WIDTH_MAX=10;
	
	public static void main(String[] args) {
		
		// 先创建一个二维数组，模拟迷宫
		// 地图
		int[][] map = new int[HIGH_MAX][WIDTH_MAX]; 
		
		// 初始化所有的墙
		init(map);
		print(map);
		
		//使用递归回溯给小球找路
		setWay(map, 1, 1); 
		print(map);
	} 
	
	private static void init(int[][] map){
	
		
		// 使用 1 表示墙
		// 上下全部置为 1 
		for (int i = 0; i < HIGH_MAX; i++) { 
			map[0][i] = 1; 
			map[9][i] = 1; 
		} 
		// 左右全部置为 1 
		for (int i = 0; i < WIDTH_MAX; i++) { 
			map[i][0] = 1; 
			map[i][9] = 1; 
		} //设置挡板, 1 表示
		map[1][3] = 1; 
		map[1][7] = 1;
		map[2][3] = 1;
		map[2][7] = 1;
		map[3][5] = 1;
		map[3][6] = 1;
		map[4][2] = 1;
		map[4][3] = 1;
		map[4][4] = 1;
		map[5][4] = 1;
		map[6][2] = 1;
		map[6][6] = 1;
		map[7][2] = 1;
		map[7][3] = 1;
		map[7][4] = 1;
		map[7][7] = 1;
		map[7][7] = 1;
		map[8][1] = 1;
		
	}
	
	private static void print(int[][] map){
		// 输出地图
		System.out.println("地图的情况"); 
		for (int i = 0; i < WIDTH_MAX; i++) { 
			for (int j = 0; j < HIGH_MAX; j++) { 
				System.out.print(map[i][j] + " ");
			} 
			System.out.println(); 
		} 
	}
		
	//使用递归回溯来给小球找路
	//说明
	//1. map 表示地图
	//2. i,j 表示从地图的哪个位置开始出发 (1,1) 
	//3. 如果小球能到 map[WIDTH_MAX-2][HIGH_MAX-2] 位置，则说明通路找到.
	//4. 约定： 当 map[i][j] 为 0 表示该点没有走过 当为 1 表示墙； 2 表示通路可以走 ； 3 表示该点已经走过，但是走不通
	//5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
	/** 
	* 
	* @param map 表示地图
	* @param i 从哪个位置开始找
	* @param j 
	* @return 如果找到通路，就返回 true, 否则返回 false 
	*/
	public static boolean setWay(int[][] map, int i, int j) { 
		if(map[WIDTH_MAX-2][HIGH_MAX-2] == 2) { 
			// 通路已经找到 ok 
			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 { 
				// 如果 map[i][j] != 0 , 可能是 1， 2， 3 
				return false; 
			} 
		} 
	}		
	
}

最终结果：