通过递归调用解决迷宫问题

什么是迷宫？

相信大家都玩在4399里玩过迷宫游戏。
如下图

图中左上角的小猫需要到达右下角小鱼干的位置游戏才算成功。
当然我们有上帝视角非常容易可以到达小鱼干的位置获得成功。
那么我们如何让电脑帮我们去解决这个问题呢？

思路

使用递归回溯的思路来解决出迷宫的问题finway方法用来找出迷宫的路径可以把迷宫表示成一个二维数组，因为是递归找路，所以得规定map数组值的含义 0表示可以走的路 1表示障碍物 2表示可以走的路 3表示可以走但是走不通的路。
当map[8][8]=2 就说明找到通路了就结束。
相当于设置小鱼干的位置让猫去找。
确定猫找路的策略，下->右->上->左

创建迷宫用二维数组表示

int[][] map =new int [10][10]

先建立一个简单的8*8的迷宫

绘制迷宫图

因为是递归找路，所以得规定map数组值的含义
0表示可以走的路 1表示障碍物 2表示可以走的路 3表示可以走但是走不通的路
当map[8][8]=2 就说明找到通路了 结束

 int [][]map =new int [10][10];//最上面一行和最下面一行，全部设置为1for (int i =0;i < 10;i++){map [0][i] = 1;map [9][i] = 1;}//最左边的一列和最右边的一列，全部设置为1for (int i = 0;i < 10; i++){map [i][0] = 1;map [i][9] = 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();}

运行结果为

设置障碍物

这里是我随意设置的障碍物

		map [3][1] = 1;map [6][4] = 1;map [3][4] = 1;map [3][5] = 1;map [2][6] = 1;map [4][7] = 1;map [5][9] = 1;map [5][8] = 1;map [6][6] = 1;map [4][3] = 1;map [4][4] = 1;map [7][7] = 1;map [5][5] = 1;map [8][1] = 1;map [7][3] = 1;map [7][5] = 1;map [8][5] = 1;

运行结果为

寻找路的方法

class T {public boolean finway(int [][]map ,int i, int j){if(map[8][8] == 2){//说明找到return true;}else {if (map[i][j] == 0) {//不妨设可以走通map[i][j] = 2;//使用策略if (finway(map,i + 1, j)) {return true;} else if (finway(map, i, j + 1)) {return true;} else if (finway(map, i - 1, j)) {return true;} else if (finway(map, i, j - 1)) {return true;} else {map[i][j] = 3;}}}return false;}
}

总代码

public class Migong {public static void main(String[] args) {int [][]map =new int [10][10];for (int i =0;i < 10;i++){map [0][i] = 1;map [9][i] = 1;}for (int i = 0;i < 10; i++){map [i][0] = 1;map [i][9] = 1;}map [3][1] = 1;map [6][4] = 1;map [3][4] = 1;map [3][5] = 1;map [2][6] = 1;map [4][7] = 1;map [5][9] = 1;map [5][8] = 1;map [6][6] = 1;map [4][3] = 1;map [4][4] = 1;map [7][7] = 1;map [5][5] = 1;map [8][1] = 1;map [7][3] = 1;map [7][5] = 1;map [8][5] = 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();}T t = new T();t.finway(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();}}
}class T {public boolean finway(int [][]map ,int i, int j){if(map[8][8] == 2){//说明找到return true;}else {if (map[i][j] == 0) {//不妨设可以走通map[i][j] = 2;//使用策略if (finway(map,i + 1, j)) {return true;} else if (finway(map, i, j + 1)) {return true;} else if (finway(map, i - 1, j)) {return true;} else if (finway(map, i, j - 1)) {return true;} else {map[i][j] = 3;}}}return false;}
}

最终的运行结果

所找到的路径

递归回溯

在此处运用到了递归回溯

当程序运行到此处时，发现走不通，那么将会返回到上一个栈的findway方法中执行这一部分中的语句。

如果四个方向都走不通那么将此处设置为3。再次进行回溯。