Java数据结构 递归之迷宫回溯 Java数据结构 递归之迷宫回溯案例讲解
去吧猫头夜鹰 人气:0想了解Java数据结构 递归之迷宫回溯案例讲解的相关内容吗，去吧猫头夜鹰在本文为您仔细讲解Java数据结构 递归之迷宫回溯的相关知识和一些Code实例，欢迎阅读和指正，我们先划重点：Java数据结构,Java数据结构,递归之迷宫回溯，下面大家一起来学习吧。
问题介绍：
用二维数组表示一个迷宫，设置迷宫起点和终点，输出迷宫中的一条通路
实现思路：
二维数组表示迷宫：
0表示路且未走过、1表示墙、2表示通路，3表示已经走过但走不通
设置寻路方法setWay，传入地图和坐标参数
默认方向策略：下、右、上、左
假定传入的店没有走过且可以走通，将其值置为2，然后向下寻路，也就是将坐标 (i + 1, j) 传入寻路方法中
进行递归寻路，向下移动后，再次按照方向策略进行寻路，即再向下寻路，直到遇到死路，即下右左均走不通（因为将走过的路置为2，故向上也走不通，即遇到死路时回头不算通路），则将该点置为3，并返回false，回到上一个递归，找寻方向策略中剩下的方向，实现回溯
代码实现：
public class Maze {
public static void main(String[] args) {
maze();
}
//迷宫回溯问题
public static void maze() {
//创建二维数组模拟迷宫
//使用1表示墙，0表示路
int[][] map = new int[][]{
{1, 1, 1, 1, 1, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 0, 1, 0, 0, 0, 1},
{1, 0, 1, 0, 1, 1, 1},
{1, 1, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 0, 1, 1},
{1, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1}
};
//输出地图
System.out.println("迷宫：");
for (int[] row : map) {
for (int i : row) {
System.out.printf("%d\t", i);
}
System.out.println();
}
System.out.println("寻路结果：");
//开始寻路
setWay(map, 1, 1);
//输出地图
for (int[] row : map) {
for (int i : row) {
System.out.printf("%d\t", i);
}
System.out.println("");
}
}
//传入地图map
//传入开始位置(i, j)
//如果能到达右下角(6, 5)，则说明找到通路
//0表示未走过，1表示墙，2表示可以走的通路，3表示已经走过，但是走不通
//确定方向策略：下 -> 右 -> 上 -> 左
//若该点走不通，则回溯
public static boolean setWay(int[][] map, int i, int j) {
if (map[6][5] == 2) {
//通路已经找到
return true;
} else {
if (map[i][j] == 0) {
//如果当前点没有走过
map[i][j] = 2; //假定该点可以走通
if (setWay(map, i + 1, j)) {
//向下走
return true;
} else if (setWay(map, i, j + 1)) {
//向右走
return true;
} else if (setWay(map, i - 1, j)) {
//向上走
return true;
} else if (setWay(map, i, j - 1)) {
//向左走
return true;
} else {
//该点走不通
map[i][j] = 3;
return false;
}
} else {
//如果map[i][j] != 0
//可能是1、2、3
return false;
}
}
}
}
输出结果：
迷宫： 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 寻路结果： 1 1 1 1 1 1 1 1 2 2 2 0 0 1 1 3 1 2 0 0 1 1 3 1 2 1 1 1 1 1 0 2 2 0 1 1 0 1 1 2 1 1 1 0 0 0 2 2 1 1 1 1 1 1 1 1
加载全部内容