7121人阅读
有意思的程序练习题（15）
问题：有一个迷宫，在迷宫的某个出口放着一块奶酪。将一只老鼠由某个入口处放进去，它必须穿过迷宫，找到奶酪。请找出它的行走路径。
解法：这个问题可以用递归的方法去求解。
&&&&&&& 先来看下面这幅图：
&&&&&&& 绿色箭头指向的是迷宫的入口，将小老鼠由此放入，红色箭头的位置就是奶酪的所在地，小老鼠必须穿过迷宫从红色箭头标示的地方走出去。
我们用一个二维数组来表示迷宫，用2表示迷宫的墙壁，即上图中的黑色部分，用0表示通路，即上图中老鼠可以行走空白的格子。老鼠每走到一个格子的时候就将该位置的值置为1，表示老鼠的行走路径包括这个格子。
&&&&&&& 接下来说一下老鼠的行走策略：老鼠每走一步（格子）的时候，将该格子的值置为1，然后会依次考察该格子的右、下、左、上位置的格子是否可走（可走的标志是该格子的值为0）。这样老鼠从入口的格子出发，就会派生出很多可能的行走路径，如果某一条路不能走到终点的话，那么就要将相应的格子的值重新置为0了，表示正确的路径不包括这个格子。
&&&&&&& 好了，终于到具体的实现代码了：
public class Mouse {
public static void main(String[] args) {
int[][] maze={{2,2,2,0,2,2,2,0,0},
{2,0,0,0,0,0,2,0,0},
{2,0,2,2,2,2,2,2,2},
{0,0,0,0,0,0,0,0,2},
{2,0,2,2,2,2,0,2,2},
{2,0,2,2,0,0,0,2,2},
{2,0,2,2,0,2,2,0,2},
{2,0,2,0,0,0,0,0,0},
{2,0,2,2,2,2,2,2,2}
Map map=new Map(maze, new Point(7, 8));
Mouse.go(map, new Point(0,3));
map.print();
public static void go(Map map,Point p){
map.step(p);
if(p.y&map.maze[0].length-1)
test(map,new Point(p.x, p.y+1));
if(p.x&map.maze.length-1)
test(map,new Point(p.x+1, p.y));
if(p.y&=1)
test(map,new Point(p.x, p.y-1));
if(p.x&=1)
test(map,new Point(p.x-1, p.y));
if(!map.isArrived())
map.empty(p);
public static void test(Map map,Point p){
if(!map.isArrived() && map.isEmpty(p)){
go(map,p);
class Point{
public Point(int x1,int y1){
class Map{
public Map(int[][] maze,Point end){
this.maze=
//是否到达终点
public boolean isArrived(){
return maze[end.x][end.y]==1;
//当前这一格是否可行
public boolean isEmpty(Point p){
return maze[p.x][p.y]==0;
//可以理解为当经过Point p 无法走到终点时，把老鼠走过的痕迹抹去，表示最终的走法不含p
public void empty(Point p){
maze[p.x][p.y]=0;
//走到Point p
public void step(Point p){
maze[p.x][p.y]=1;
//打印地图，含老鼠走过的路径
public void print(){
for(int i=0;i&maze.i++)
for(int j=0;j&maze[0].j++)
if(maze[i][j]==2){
System.out.print(&█&);
}else if(maze[i][j]==0){
System.out.print(& &);
}else if(maze[i][j]==1){
System.out.print(&1&);
System.out.println();
&&&&&& 运行结果如下：
可见，小老鼠成功地走到了终点。
&&&&&&& 如果迷宫的设计使得走法不止一种，则只要在老鼠走至出口时显示出所有的路径，然后退回上一格重新选择下一个位置继续递归就可以了。如下图有两种走法。
代码作了一点点儿修改：
public class Mouse {
public static void main(String[] args) {
int[][] maze={{2,2,2,0,2,2,2,0,0},
{2,0,0,0,0,0,2,0,0},
{2,0,2,2,2,0,2,2,2},
{0,0,0,0,0,0,0,0,2},
{2,0,2,2,2,2,0,2,2},
{2,0,2,2,0,0,0,2,2},
{2,0,2,2,0,2,2,0,2},
{2,0,2,0,0,0,0,0,0},
{2,0,2,2,2,2,2,2,2}
Map map=new Map(maze, new Point(7, 8));
Mouse.go(map, new Point(0,3));
//map.print();
public static void go(Map map,Point p){
map.step(p);
if(map.isArrived())
map.print();
map.maze[map.end.x][map.end.y]=0;
if(p.y&map.maze[0].length-1)
test(map,new Point(p.x, p.y+1));
if(p.x&map.maze.length-1)
test(map,new Point(p.x+1, p.y));
if(p.y&=1)
test(map,new Point(p.x, p.y-1));
if(p.x&=1)
test(map,new Point(p.x-1, p.y));
map.empty(p);
public static void test(Map map,Point p){
if(!map.isArrived() && map.isEmpty(p)){
go(map,p);
class Point{
public Point(int x1,int y1){
class Map{
public Map(int[][] maze,Point end){
this.maze=
//是否到达终点
public boolean isArrived(){
return maze[end.x][end.y]==1;
//当前这一格是否可行
public boolean isEmpty(Point p){
return maze[p.x][p.y]==0;
//可以理解为当经过Point p 无法走到终点时，把老鼠走过的痕迹抹去，表示最终的走法不含p
public void empty(Point p){
maze[p.x][p.y]=0;
//走到Point p
public void step(Point p){
maze[p.x][p.y]=1;
//打印地图，含老鼠走过的路径
public void print(){
for(int i=0;i&maze.i++)
for(int j=0;j&maze[0].j++)
if(maze[i][j]==2){
System.out.print(&█&);
}else if(maze[i][j]==0){
System.out.print(& &);
}else if(maze[i][j]==1){
System.out.print(&1&);
System.out.println();
System.out.println();
运行结果：
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：366920次
积分：4507
积分：4507
排名：第5600名
原创：105篇
转载：27篇
评论：98条
(1)(1)(1)(7)(1)(4)(2)(5)(8)(1)(4)(4)(6)(1)(4)(2)(2)(1)(3)(4)(2)(5)(5)(1)(1)(2)(6)(11)(7)(5)(1)(6)(1)(4)(14)查看: 589|回复: 9
战士, 积分 1206, 距离下一级还需 294 积分
精华0帖子威望0 点积分1206 点注册时间最后登录
左上角迷宫地图显示不了，是不是遇到bug了，迷宫跑了几次了，地下打过巨人了？地图也基本踏破了，出来还是一样，会不会是漏了迷宫什么地方？最后钥匙房间右边在小地图显示暗的
(198.56 KB, 下载次数: 0)
00:44 上传
下载次数: 0
战士, 积分 777, 距离下一级还需 723 积分
精华0帖子威望0 点积分777 点注册时间最后登录
我也不显示，不知道为什么，可能要打了隐藏迷宫才显示吧?
游民, 积分 7, 距离下一级还需 3 积分
精华0帖子威望0 点积分8 点注册时间最后登录
一直摸索到隐藏迷宫门口就显示了
战士, 积分 1206, 距离下一级还需 294 积分
精华0帖子威望0 点积分1206 点注册时间最后登录
死之天使 发表于
我也不显示，不知道为什么，可能要打了隐藏迷宫才显示吧?
其他迷宫都打了，钥匙任务也能接，就是不显示
公民, 积分 245, 距离下一级还需 55 积分
精华0帖子威望0 点积分245 点注册时间最后登录
因为你没有找到要钥匙开的门所以不显示。
战士, 积分 1206, 距离下一级还需 294 积分
精华0帖子威望0 点积分1206 点注册时间最后登录
huangxu111 发表于
因为你没有找到要钥匙开的门所以不显示。
找到了啊，隐藏迷宫钥匙任务也接了就是不显示
战士, 积分 777, 距离下一级还需 723 积分
精华0帖子威望0 点积分777 点注册时间最后登录
深苍 发表于
找到了啊，隐藏迷宫钥匙任务也接了就是不显示
你要进去啊，开了那个隐藏迷宫门以后。单拿到钥匙没用，得到里面开那个隐藏门之后
战士, 积分 1206, 距离下一级还需 294 积分
精华0帖子威望0 点积分1206 点注册时间最后登录
死之天使 发表于
你要进去啊，开了那个隐藏迷宫门以后。单拿到钥匙没用，得到里面开那个隐藏门之后 ...
ok，我以为跟其他一样，整个迷宫探索就显示在地图上了
战士, 积分 821, 距离下一级还需 679 积分
精华0帖子威望0 点积分821 点注册时间最后登录
这个点好像就是这么奇怪不显示，昨晚做讨伐来了这里心想这里有个迷宫我没发现？？
原来就是之前剧情那个
战士, 积分 1206, 距离下一级还需 294 积分
精华0帖子威望0 点积分1206 点注册时间最后登录
<font color="#04c1501 发表于
这个点好像就是这么奇怪不显示，昨晚做讨伐来了这里心想这里有个迷宫我没发现？？
原来就是之前剧情那个 ...
对啊 里面要站触发几个机关能把落下的石头升回去 还有路的
Powered by
扫描二维码
下载 A9VG 客户端（iOS, Android）}