递归回溯 |
您所在的位置：网站首页 › 芒康县如美镇水电站 › 递归回溯 |
递归回溯
|
目录 前言 设计思路 绘制地图 寻找出路 绘制路线 总结 前言这是一道关于递归回溯的经典题目，在布下障碍的迷宫中，为老鼠朋友找到一条可以逃出困境的路线，本文将为大家详细讲解如何运行递归的方法让老鼠走出迷宫。 （注：1.文中代码段由作者自己编写，若有纰漏或错误，欢迎大家指正；2.文中部分代码段仅为参考模板，请朋友们根据需求进行修改；3.作者本人为初学者，编程水平有待提高，所写博客皆为本人的笔记和一些简单知识的分享，还望各位路过的大佬嘴下留情） 设计思路首先，我们需要绘制一张8行7列的地图，并且布下种种障碍，绿点为老鼠，红旗为迷宫出口。 其次，我们定义一个方法，这个方法的作用便是为老鼠寻找出路，在方法中反复递归，不断尝试上下左右这四个方向的路是否能走通，能够走通的路在原地标记2，不能走通的路便在原地标记3。 最后，调用这个方法，重新绘制地图，这时我们原先的迷宫地图已经被修改为画有出逃路线的地图 大体思路就是如此，下面我将为大家讲解具体的操作以及代码实现。 绘制地图我们需要定义一个二维数组绘制一张8行7列的地图，并在这张迷宫地图上布下障碍，如下图： 首行、列及尾行、列是我们的墙，坐标（4,2）、（4,3）的方块是我们的障碍物。 我们先来绘制障碍物，并将障碍物所在的坐标赋值为1： //定义一个8行7列的二维数组 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; //(4,2),(4,3)为障碍物当我们将障碍物布置好后，再来对这个二维数组进行遍历打印地图： //绘制地图 for(int i = 0; i < map.length; i++) { for(int j = 0; j < map[i].length; j++) { System.out.print(map[i][j] + " ");//遍历数组输出各个元素 } System.out.println(); //每输出一行进行换行 }来看看地图的效果，1表示障碍物 ，0表示可以尝试走的路：
这样一来，我们的初始迷宫地图便绘制好了。 寻找出路我们定义一个返回类型为布尔型的数值的方法findWay来寻找出路： //寻找出路 public static boolean findWay(int[][] map , int i , int j) { if(map[6][5] == 2) return true; //找到出口 else { if(map[i][j] == 0) { map[i][j] = 2; //标记此处可行 if(findWay(map , i+1 , j)) //向下寻找出路,返回真值继续递归找出路，返回假值执行下列语句 return true; else if(findWay(map , i , j+1)) //向右寻找出路 return true; else if(findWay(map , i-1 , j)) //向上寻找出路 return true; else if(findWay(map , i , j-1)) //向左寻找出路 return true; else { map[i][j] = 3; return false; //找不到出路，在此处标记为3 } } else return false; } }让我为大家分析一下这个方法如何通过递归反复尝试找到逃出迷宫的路线： 首先，我们定义一个方法，方法名为findWay，且返回的数值为布尔型的数据类型，我们需要传入的参数为一个表示地图的二维数组map，以及行i和列j。 上文已经说过，当老鼠所在的路能够走通时，便在原处标记为2。 第一重if...else语句：所以，我们进入方法中查看，设置一个if...else语句，当迷宫出口map[6][5] == 2时，表示我们已经成功到达出口，返回一个true值，离开方法；如果map[6][5] != 2时，便进行不同方向的递归调用。 第二重if...else语句：在else语句中嵌套一个if...else语句，如果老鼠所在处为0，即还没有走过的路，便执行if中的语句；如果不为0，便返回一个false值。 第三重if...else语句：在if语句中再嵌套一个if...else语句，进行下→右→上→左方向的尝试： 当老鼠所在处为0时，我们便在此处标记为2，表示此处可行； 首先，我们尝试向下走，调用方法findWay(map , i+1 , j)，i+1表示行数加一，向下走； 判断此时所在地是否为2，如果不为2，执行else中的语句； 再判断此时所在地是否为0，如果为0，便将原地标记为2，表示此处可行，继续调用方法findWay(map , i+1 , j)，向下走；如果不为2，便返回一个false值给if(findWay(map , i+1 , j))，继续执行if(findWay(map , i+1 , j))后的else if语句，尝试接着向右、上、左方向走。 一直如此反复递归，直到map[6][5] == 2时，我们便成功找到通往迷宫出口的路线了。 绘制路线此时我们已经找到通往迷宫出口的路线了，接着便是调用方法findWay，重新遍历数组绘制路线： //绘制路线 System.out.println("寻找出路"); for(int i = 0; i < map.length; i++) { for(int j = 0; j < map[i].length; j++) { System.out.print(map[i][j] + " "); } System.out.println(); }绘制的路线图如下：
如此一来，我们便成功地帮助鼠鼠找到了迷宫出口。 这里为大家提供完整的代码： public class Text { public static void main(String[] args) { //绘制地图 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; //(4,2),(4,3)为障碍物 //打印地图 System.out.println("初始地图"); for(int i = 0; i < map.length; i++) { for(int j = 0; j < map[i].length; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } System.out.println(); //换行 //调用方法 传入参数 设起始地为(1,1) findWay(map , 1 , 1); //绘制路线 System.out.println("寻找出路"); for(int i = 0; i < map.length; i++) { for(int j = 0; j < map[i].length; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } } //寻找出路 public static boolean findWay(int[][] map , int i , int j) { if(map[6][5] == 2) return true; //找到出口 else { if(map[i][j] == 0) { map[i][j] = 2; //标记此处可行 if(findWay(map , i+1 , j)) //向下寻找出路,返回真值继续递归找出路，返回假值执行下列语句 return true; else if(findWay(map , i , j+1)) //向右寻找出路 return true; else if(findWay(map , i-1 , j)) //向上寻找出路 return true; else if(findWay(map , i , j-1)) //向左寻找出路 return true; else { map[i][j] = 3; return false; //找不到出路，在此处标记为3 } } else return false; } } }运行结果如下： 言语粗糙，不堪理解，讲的不够好，有不足之处望大家能够慷慨指出，感谢！ |
【本文地址】
今日新闻 |
推荐新闻 |