Java递归实现迷宫游戏

Java递归实现迷宫游戏

目录1.问题由来2.问题的描述3.思路分析4.代码实现5.结果输出

1.问题由来

迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到

老鼠从入口到出口，而不

GKxKUesS

走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。

2.问题的描述

有一个迷宫地图，有一些可达的位置，也有一些不可达的位置（障碍、墙壁、边界）。从一个位置到下一个位置只能通过向上（或者向右、或者向下、或者向左）走一步来实现，从起点出发，如何找到一条到达终点的通路。

3.思路分析

本文通过按照约定的策略（比如下->右->上->左）不停的递归调用方法寻找迷宫的出口。从起点出发，每个位置都有四种选择（上右下左），先选择一个方向（按约定的顺序选择优先方向），如果该方向能够走下去，那么就往这个方向走，当前位置切换为下一个位置。如果不能走，那么换个方向走，如果所有方向都走不了，那么就回到到上一个位置去。一直这样执行下去，如果当前位置是终点，就退出程序

用二维数组来模拟迷宫地图

1代表墙壁

0代表该位置可达。

2代表每走过一个位置就将地图的http://对应位置标记 以免重复

3代表走过这个位置但是走不通

4.代码实现

public class MiGong {

public static void main(String[] args) {

int[][] map = new int[8][8];

/**

* 初始化迷宫

*/

for (int i = 0; i < 8; i++) {

map[0][i] = 1;

map[7][i] = 1;

map[i][0] = 1;

map[i][7] = 1;

}

for (int i = 0; i < 4; i++) {

map[3][1+i] = 1;

map[5][6-i] = 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();

}

getWay(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();

}

}

public static boolean getWay(int[][] map,int i,int j){

if (map[6][6] == 2){ //已经到达终点

return true;

}else {

if (map[i][j] == 0){ //当前位置还没走过

map[i][j] = 2;

if (getWay(map,i+1,j)){ //向下走

return true;

}

if (getWay(map,i,j+1)){ //向右走

return true;

}

if (getWay(map,i,j-1)){ //向左走

return true;

}

if (getWay(map,i-1,j)){ //向上走

return true;

}else{

map[i][j] = 3; //四边都走不通

return false;

}

}else{ //如果不是0就说明过不了或者走过了

return false;

}

}

}

}

5.结果输出

由于按照下->右->上->左的约定顺序取判定下一步是否可走

在到达（4,5）位置时会向向右走黄色的那条路线 当走到（1,2）

位置时四周都不为0即四边都不可走那么它就会退回到上一个位置

回到（1,3）后发现四周依旧不可达依此规则直至回到（4，5）

最终行走的路线就为红线所示：

按照不同的策略有不同的行走路线

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