递归-迷宫问题

?迷宫问题

package recursion;

//求最短路径？
public class MiGong {
//用递归解决迷宫问题
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 先写一个地图
		int[][] map = new int[8][7];
		for (int i = 0; i < 7; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}
		for (int i = 0; i < 8; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		map[3][1] = 1;
		map[3][2] = 1;
		// 产生回溯
		// map[1][2] = 1;
		// map[2][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();
		}
		setWay(map, 1, 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();
		}
	}

	// 开始启动
	/**
	 * 
	 * @param map 表示地图
	 * @param i   （i，j） 表示从哪个位置开始走
	 * @param j
	 * @return 找到就返回true 否则就返回false 走到（6，5）就找到了 约定：当map[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 {// 不等于0 ，那么就是1（是墙，走不通） 或 2(这个点已经走过) 或 3（死路一条）
				return false;// 返回false;
			}
		}
	}
}

运行结果：

原来的地图为：
1 1 1 1 1 1 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 1 1 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 0 0 0 0 0 1 
1 1 1 1 1 1 1 
小球走过并标识的地图：
1 1 1 1 1 1 1 
1 2 0 0 0 0 1 
1 2 2 2 0 0 1 
1 1 1 2 0 0 1 
1 0 0 2 0 0 1 
1 0 0 2 0 0 1 
1 0 0 2 2 2 1 
1 1 1 1 1 1 1 

问题1：自己解决最短的出迷宫的路线

问题2：理解并解决八皇后问题

未完待续。。。?