小球走迷宫

  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 }

 

上一篇:从零开始学习Spring - SpringMVC组件概述、请求解析、响应解析、静态资源


下一篇:SpringMVC