小迷宫的递归实现(小球到达终点的路径)
最编程
2024-06-29 21:24:11
...
使用递归来实现小球找到终点的过程
主要需要注意:1、使用递归时必须得有一个退出递归的条件,并且递归的不断调用应该使的越来越靠近这个条件,否则就是死循环。
2、由于递归的调用次数很多,则需要遵循谁调用,就把结果返回给谁,然后继续执行。
3、递归不断的在栈中加入方法,如果是死循环则会导致栈溢出的错误。
4、递归调用的函数在栈中是先执行最外面的,然后执行里面的,类似于阶乘的实现。
代码如下:
1 package com.pangzi.stucture; 2 3 public class MiGong { 4 5 public static void main(String[] args) { 6 //创建一个二维数组,模拟迷宫,8行7列 7 8 int[][] map = new int[8][7]; 9 10 //使用1表示樯,把上下置为1,第一行和第8行都为1 11 for(int i = 0;i < 7;i++){ 12 map [0][i] = 1; 13 map [7][i] = 1; 14 } 15 16 //把左右置为1 17 for(int i = 0;i < 8;i++){ 18 map [i][0] = 1; 19 map [i][6] = 1; 20 } 21 22 //设置挡板 第四行第二列,和第四行第三列 23 map [3][1] = 1; 24 map [3][2] = 1; 25 26 //输出地图 27 for(int i = 0;i < 8;i++){//遍历行 28 for(int j = 0;j < 7;j++){//遍历列 29 System.out.print(map[i][j] + " "); 30 } 31 System.out.println(); 32 } 33 34 //使用递归找路 35 setWay(map,1,1); 36 37 //输出新的地图,小球走过并且标识过的路线 38 System.out.println("小球走过的路"); 39 for(int i = 0;i < 8;i++){//遍历行 40 for(int j = 0;j < 7;j++){//遍历列 41 System.out.print(map[i][j] + " "); 42 } 43 System.out.println(); 44 } 45 46 } 47 48 //使用递归回溯来给小球找路,小球要去右下角,给方法传入地图和小球的开始位置,如果找到了通路返回true 49 //说明:map 是地图 50 //i,j是小球的开始位置(1,1) 51 //如果小球到int[6][5]则说明到终点了,找到路了 52 //当地图的map[i][j]的值为0时,表示该点没有走过,当为1时为樯,当为2时表示可以走,当为3时表示该位置已经走过了,但是走不通 53 //在走迷宫时,需要先去确定一个策略(方法) 下-》右-》上-》左 ,如果该点走不通,再回溯 54 public static boolean setWay(int[][] map,int i,int j){ 55 if(map[6][5] == 2){//说明找到了终点 56 return true; 57 }else{ 58 if(map[i][j] == 0){//如果这里还没有走过 59 //按照实现定好的策略进行操作 下-》右-》上-》左 60 map[i][j] = 2;//假设该点可以走通 61 if(setWay(map,i+1,j)){//从这个点开始向下走 62 return true; 63 }else if(setWay(map,i,j+1)){//向下走不通就向右走 64 return true; 65 }else if(setWay(map,i-1,j)){//向右走不通就向上走 66 return true; 67 }else if(setWay(map,i,j-1)){//向上走不通就向左走 68 return true; 69 }else{//如果上下左右都走不通,那么这就是走不通的点,设置值为3 70 map [i][j] = 3; 71 return false; 72 } 73 }else{//如果map[i][j]不为0,可能是1樯、2走过了、3走不通 74 return false; 75 } 76 } 77 } 78 79 80 81 82 }
上一篇: 迷宫回溯
推荐阅读