java 实现迷宫回溯算法示例详解
更新时间已经设定成了二零二零年的七月三十一号的早上九点五十三分五十秒, 作者这个名称叫做Lzfa。
这篇文章的主要内容是对利用java语言来编写迷宫回溯算法的示例部分进行详细介绍, 文章中提供的示例代码内容十分详细, 这对于大家开展学习或实际工作具有一定的参考和帮助价值, 所以有需要了解的朋友们可以跟随接下来要介绍的内容一同开展学习相关的知识。
使用一个大小为7除以7的矩形来对迷宫进行表示, 其中数值0用来指代通路, 数值1则用来指代障碍。需要通过设计并编写相应的程序, 来寻找出一条路线, 使得蓝色小球能够移动到蓝色旗子所在的位置。
把思路进行改写。
建立一个迷宫, 这个迷宫是使用二维数组来呈现的, 然后去实现那个能够找出一条通路的方法。
构建一个二维数组, 这个操作并不难。我们主要是要实现括号包裹的那个方法。在去实现这个方法之前, 咱们需要约定好下面这几个点。具体来说, 把小球所在的位置当作入口, 也就是坐标（1, 1）。同样地, 把小旗所在的位置当作出口, 也就是坐标（5, 5）。
另外, 数组里的数字, 它们的含义分别对应着几种情况: 如果数字是0, 代表没有走过；如果数字是1, 代表那里有障碍；如果数字是2, 代表走过这一格算是正确路线的一部分；如果数字是3,代表走过这一格但属于错误的路线。
我们将每走一步所采取的方式, 称为策略, 而咱们的行走顺序规则定为: 先往下走, 再往右走, 接着往上走, 最后往左走。
实现
第一步, 我们需要构建出一份迷宫出来。
public static void main(String[] args) {
//1.创建二维数组模拟迷宫
int[][] maze = new int[7][7];
//2.初始化迷宫
for (int i = 0; i < maze.length; i++) {
//maze[i][j]:i控制行 j:控制列
maze[0][i] = 1;//第1行都为1
maze[6][i] = 1;//最后一行都为1
maze[i][0] = 1;//第一列都为1
maze[i][6] = 1;//最后一列都为1
//其他位置的1
maze[4][1] = 1;
maze[4][2] = 1;
maze[4][3] = 1;
maze[4][4] = 1;
maze[3][4] = 1;
maze[2][3] = 1;
}
//打印迷宫
System.out.println("完成迷宫初始化：");
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[i].length; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println();
}
}
然后写()方法
* 使用递归回溯找通路 （5，5为出口）
* @param maze 迷宫
* @param i 从哪个位置开始找
* @param j 从哪个位置开始找
* @return 找到通路返回true 否则false
*/
public static boolean findRoad(int[][] maze, int i, int j) {
//策略：下 -> 右 -> 上 ->左
//0：没有走过 1：障碍 2:走过且为正确的路线 3：走过且为错误的路线
if (maze[5][5] == 2) {//找到通路
return true;
} else {
if (maze[i][j] == 0) {
//当前点没走过，按策略走
maze[i][j] = 2;//当前点改为2，假定能走通
if (findRoad(maze, i + 1, j)) {//向下走
return true;
} else if (findRoad(maze, i, j + 1)) {//向右走
return true;
} else if (findRoad(maze, i - 1, j)) {//向上走
return true;
} else if (findRoad(maze, i, j - 1)) {//向左走
return true;
} else {
//该点无法走通
maze[i][j] = 3;
return false;//返回到上个方法（即返回到上个点）
}
} else {
//该点为 1或2或3，无法走通，直接返回上个方法（即上个点）
return false;
}
}
}
main方法会去调用那个括号里面应该填写的方法, 在这个调用的过程之中, 它需要把已经创建好了的迷宫传进去, 同时还要把代表入口点的坐标一跟坐标一一作为参数传输过去。
//mian方法中调用findRoad()方法
findRoad(maze,1,1);
//打印迷宫
System.out.println("完成路线的迷宫：");
for (int i = 0; i < maze.length; i++) {
for (int j = 0; j < maze[i].length; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println();
}
效果
到这里为止, 这篇讲解利用java来实现迷宫回溯算法的具体示例教程已经介绍完毕了。如果你想了解关于用java实现迷宫回溯算法的更多内容, 欢迎去搜索脚本之家以往发布过的相关文档, 或者继续浏览下面推荐的其他关联文章。我们衷心希望各位读者在将来能够一如既往地支持脚本之家这个平台！
