Java—递归（迷宫问题）适合小白

阅读：评论：0

Java—递归（迷宫问题）适合小白

迷宫问题

一、问题描述：

有一个8 ×7的迷宫，如图所示，现在有一个小球需要从左上角运动到右下角，请找出一条路。

地图描述：红色区域为墙，小球不能通过，小球只能在白色区域移动

二、问题解决

在这个问题中，我们用递归来解决，起始位置为第一行第一列，小球每次移动可以向上、左、下、右这四个方向移动，并且这四个方向等可能，我们可以制定小球移动策略，这里我规定小球以 右-上-左-下 的策略移动，即小球先向有移动，当向右不能在移动之后，小球再向上移动，依此类推、、、
我们先将地图数字化，转化为一个8×7的数组：
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 1 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 1 0 1 1 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

1：表示地图中的墙，0表示地图中小球可以走的白色区域

为了分清小球在地图中那些地方可以走，那些地方不可以走，那些地方走过，我们须得做一个约定，便于识别。值得注意的是，“走过” 又有两种情况，即、走到这个地方，还可以继续走（走得通）；也有另一种情况，走到死胡同（走不通），所以我们在做约定的时候要分两种情况。

约定：

小球不能走的地方，即墙，我们在数组中用 ” 1 “ 来标识；
小球可以走的地方，即白色区域，我们在数组中用 ” 0 “ 来标识；
小球走的通的地方，我们在数组中用 ” 2 “ 来标识；
小球能走，但走不通的地方，我们在数组中用 ” 3 “ 来标识；

代码：

package recursion;public class MiGong {public static void main(String[] args) {//		要求：从第一行第一列出发到达右下角
//		1.创建地图
//		2.制定策略：右-上-左-下
//		3.地图说明：0表示可以走，1表示墙，2表示通路，3表示走过但不通//		创建一个二维数组用于模拟地图int[][] Map = new int[8][7];
//		初始化地图
//		地图中的挡板Map[2][3] = 1;Map[3][1] = 1;Map[3][2] = 1;Map[5][2] = 1;Map[5][4] = 1;Map[5][5] = 1;
//		做地图中的上下墙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;}//		输出地图System.out.println("地图情况~~");for (int i = 0; i < 8; i++) {for (int j = 0; j < 7; j++) {System.out.print(Map[i][j] + " ");}System.out.println();}Recursion(Map, 1, 1);
//		输出走过的地图System.out.println("走过后的地图情况~~");for (int i = 0; i < 8; i++) {for (int j = 0; j < 7; j++) {System.out.print(Map[i][j] + " ");}System.out.println();}}//	递归回溯寻找通路public static boolean Recursion(int Map[][], int i, int j) {if (Map[6][5] == 2) {// 到达右下角即返回true 退出return true;} else if (Map[i][j] == 0) {Map[i][j] = 2;// 假定此时可以走通// 策略：右-上-左-下if (Recursion(Map, i, j + 1)) {// 向右走return true;} else if (Recursion(Map, i + 1, j)) {// 向上走return true;} else if (Recursion(Map, i, j - 1)) {// 向左走return true;} else if (Recursion(Map, i - 1, j)) {// 向下走return true;} else {Map[i][j] = 3;// 走不通，将其值设为3，表示走过但走不通return false;}} else {// Map[i][j]不为0，即为1：墙，2：走过的路能走通，3：走过的路不能走通return false;// 能走的都走完了 即 没有可走的了}}}