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 }