1.问题由来 迷宫实验是取自心理学的一个古典实验。在该实验中,把一只老鼠从一个无顶大盒子的门放入,在盒中设置了许多墙,对行进方向形成了多处阻挡。盒子仅有一个出口,在出
1.问题由来 迷宫实验是取自心理学的一个古典实验。在该实验中,把一只老鼠从一个无顶大盒子的门放入,在盒中设置了许多墙,对行进方向形成了多处阻挡。盒子仅有一个出口,在出口处放置一块奶酪,吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。 2.问题的描述 有一个迷宫地图,有一些可达的位置,也有一些不可达的位置(障碍、墙壁、边界)。从一个位置到下一个位置只能通过向上(或者向右、或者向下、或者向左)走一步来实现,从起点出发,如何找到一条到达终点的通路。 3.思路分析 本文通过按照约定的策略(比如下->右->上->左)不停的递归调用方法寻找迷宫的出口。从起点出发,每个位置都有四种选择(上右下左),先选择一个方向(按约定的顺序选择优先方向),如果该方向能够走下去,那么就往这个方向走,当前位置切换为下一个位置。如果不能走,那么换个方向走,如果所有方向都走不了,那么就回到到上一个位置去。一直这样执行下去,如果当前位置是终点,就退出程序 用二维数组来模拟迷宫地图 1代表墙壁 0代表该位置可达。 2代表每走过一个位置就将地图的对应位置标记 以免重复 3代表走过这个位置但是走不通 4.代码实现 public class MiGong { getWay(map,1,1); System.out.println("======行走轨迹======"); public static boolean getWay(int[][] map,int i,int j){ 5.结果输出 由于按照下->右->上->左的约定顺序取判定下一步是否可走 在到达(4,5)位置时会向向右走黄色的那条路线 当走到(1,2) 位置时四周都不为0即四边都不可走那么它就会退回到上一个位置 回到(1,3)后发现四周依旧不可达依此规则直至回到(4,5) 最终行走的路线就为红线所示: 按照不同的策略有不同的行走路线
|
2021-06-05
2021-05-27
2021-05-26
2021-06-05
2021-05-16