1 //设置一个迷宫10X10，令小球自动走出去（递归）
2 /*
3 思路
4 1.利用一个二维数组map来表示地图,初始位置是（1,1）
5 2.数组各个值的含义
6 0表示没走过待测定，1表示走过且测定为障碍物
7 2表示走过且测定是通行的，3代表走过但是是死路
8 3.找路方法findway（）返回值为真代表找到路，为假代表是没路
9 */
10
11 public class Test{
12 public static void main(String[] args) {
13 int[][] map = new int[10][10];
14 int row = 0;int col = 0;
15 //最外一层是围墙，需要设为1
16 //上下两个围墙
17 for (;row <= 9;row++){
18 map[0][row] = 1;
19 map[9][row] = 1;
20 }
21 //左右两个围墙
22 for(col = 1;col <= 8;col++){
23 map[col][0] = 1;
24 map[col][9] = 1;
25 }
26 //随机障碍物设置10个
27 //障碍物不能是map[8][8]，不能是围墙，不能是初始化位置map[1][1]
28 int obsNum = 0;
29 for(;obsNum < 11;){
30 for(;;){
31 row = (int)(Math.random()*7 + 1);//只能取1---8范围
32 if(row == 0)
33 continue;
34 else break;
35 }
36 for(;;){
37 col = (int)(Math.random()*7 + 1);
38 if(col == 0)
39 continue;
40 else break;
41 }
42 //如果是map[8][8],map[1][1]则直接重来,如果当前坐标已经是障碍物，也重来
43 if((row == 8 && col == 8) || (row == 1 && col == 1))
44 continue;
45 else if(map[col][row] == 1)
46 continue;
47 else{
48 map[col][row] = 1;
49 obsNum++;
50 }
51 }
52 //输出地图
53 System.out.println("\n====迷宫地图如下====\n");
54 for(col = 0;col <= 9;col++){
55 for(row = 0;row <=9;row++){
56 System.out.print(map[col][row] + " ");
57 }
58 System.out.println();
59 }
60
61 //找路
62 FindWay way = new FindWay();
63 //若有通路，输出地图，否则显示没有
64 if(way.findWay(map,1,1)){
65 System.out.println("\n====通路已找到====\n");
66 for(col = 0;col <= 9;col++){
67 for(row = 0;row <= 9;row++){
68 System.out.print(map[col][row] + " ");
69 }
70 System.out.println();
71 }
72 }else{
73 System.out.println("\n====抱歉，没有通路====");
74 }
75
76 }
77 }
78
79
80 class FindWay{
81 //(col,row)为初始位置坐标
82 public boolean findWay(int[][] map,int col,int row){
83 //要确定怎么测试路径，并且什么时候才代表找到路
84 //用回溯算法，即试探法
85 //利用递归来测试路径，每一次递归是在探测下一步的情况，递归的套环就像是走了一步又一步
86 //或者数学角度来说，递归函数的结构就像是树状图，也就是把所有可能列了出来
87 //方法开头要先验证，map[8][8]变为2时证明已经走到出口，当前步为一证明是障碍物，不能立足
88 //若当前步不是障碍物，先假定当前步为2，if(findWay(...))，一直递归，
89 /*找路策略，下----右----上----左
90 上下方向相邻或者左右方向相邻明显是很低效的做法，
91 因为总会做一步无意义的判断，来判断出上一步是走过的2，
92 要知道上一步不用判断就知道是2了，不是2就不能立足探测*/
93 //如果上下左右四个方向的下一步中有出现不是障碍物或死路的，那么当前路就是2了
94 //每一步都可以选择探测上下左右，如果全都不行，那么当前map[][]赋值为3就是说这是死路
95 //如果一直是有可以走的方向，则一直返回true，这样最后这一条套环就全是2，那就是通路
96 //如果中间有障碍物，那么这一条套环会有3,3这一步的函数会返回假植给上一步，上一步则继续进行其他方向的探测
97
98 if(map[8][8] == 2)
99 return true;
100 //测试当前步是不是障碍物,不是的话就可以立足并进行下一步测量
101 if(map[col][row] != 0)
102 return false;
103 else{
104 //假定当前步为2
105 map[col][row] = 2;
106 //向下探测,若下一步是障碍物或者死路，返回假植，进行当前步的其他方向的探测
107 if(findWay(map,col + 1,row))
108 return true;
109 //向右
110 if(findWay(map,col,row + 1))
111 return true;
112 //向上
113 if(findWay(map,col - 1,row))
114 return true;
115 //向左
116 if(findWay(map,col,row - 1))
117 return true;
118 //四个方向的下一步都不行，那当前步为死路
119 else {
120 map[col][row] = 3;122 return false;
123 }
124 }
125 }
126 }