迷宫问题
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:理解并解决八皇后问题(代码简单,但理解起来很难)
未完待续。。。