Java数据结构 递归之迷宫回溯案例讲解

Java数据结构 递归之迷宫回溯案例讲解

问题介绍：

用二维数组表示一个迷宫，设置迷宫起点和终点，输出迷宫中的一条通路

实现思路：

二维数组表示迷宫：

0表示路且未走过、1表示墙、2表示通路，3表示已经走过但走不通

设置寻路方法setWay，传入地图和坐标参数

默认方sQaVtC向策略：下、右、上、左

假定传入的店没有走过且可以走通，将其值置为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);

}

Systemhttp://.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;http://

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。