ITKeyword,专注技术干货聚合推荐

注册 | 登录

数据结构的应用——使用栈实现任意迷宫的求解

baoyiming1991 分享于

2020腾讯云双十一活动,全年最低!!!(领取3500元代金券),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1073

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

推荐:数据结构之栈的应用----迷宫求解

/***********程序设计思想*************/ (1)迷宫地图相关: 利用动态二维数组来初步勾勒出迷宫: 建议先用malloc申请一维数组,再用calloc申请每个元素中的一

一个迷宫可以用如下的二维矩阵来表示

其中,1表示“墙壁”(红色部分)

0表示“通路”白色部分

黄色的单元格分别表示迷宫的入口和出口,用二维矩阵来表示则为:

{ {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 1, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 1, 0, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 1, 0, 1, 1, 0, 1}, {1, 1, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} };

推荐:数据结构:栈应用_求解迷宫问题2

/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题                                          

 

由用户输入的高和宽来随机产生的迷宫,生成二维数组,然后由随机生成的0或1来填充数组,以达到随机生成迷宫,其方法如下:

/** * 根据用户输入迷宫的高度和宽度,随机生成一个迷宫(整型二维数组)。 * @param width 迷宫的宽度。 * @param height 迷宫的高度。 */ public Maze(int width, int height) { int i; // 高度的下标索引。 int j; // 宽度的下标索引。 this.width = width; this.height = height; maze = new int[height][width]; // 新建迷宫数组,0表示可通,1表示墙壁,2表示通路。 /** * 将数组的外面一层设置“墙壁”,全1。 */ for (i = 0; i < width; ++i) { maze[0][i] = 1; maze[height - 1][i] = 1; } for (i = 0; i < height; ++i) { maze[i][0] = 1; maze[i][width - 1] = 1; } /** * 用随机数0,1填充迷宫,并设置入口和出口为0。 */ for (i = 1; i < (height - 1); ++i) { for (j = 1; j < (width - 1); ++j) { maze[i][j] = new Random().nextBoolean() ? 1 : 0; } } maze[1][1] = 0; maze[height - 2][width - 2] = 0; /* * 输出迷宫数组。 */ for (int[] w : maze) { for (int h : w) { System.out.print(h + " "); } System.out.println(); } }

 

对于路径的嗅探,我们首先创建一个Point类,来存放每个点的坐标,然后定义一个栈,来存放当前路径所经过的点,具体求解算法如下:

/** * 用来存放每个格子坐标。 * @author Bao Yiming */ class Point { public int x; public int y; Point(int x, int y) { this.x = x; this.y = y; } } ………… /** * 走迷宫。 */ public void go() { Point start = new Point(1, 1); // 迷宫入口。 Point end = new Point(width - 2, height - 2); // 迷宫出口。 int x = 1; // 初始点横坐标。 int y = 1; // 初始点纵坐标。 Stack<Point> path = new Stack<Point>(); // 用来存放路径所通过点的坐标。 path.push(start); // 将迷宫入口压入栈中。 do { boolean flag = false; /** * 向右->下->左->上的顺序探测是否有通路。 */ if (maze[x + 1][y] == 0) { maze[x + 1][y] = 2; // 当有通路是,标记该通路,以免以后重走。 path.push(new Point(x + 1, y)); // 将新通路的坐标压入路径栈中。 flag = true; } else if (maze[x][y + 1] == 0) { maze[x][y + 1] = 2; path.push(new Point(x, y + 1)); flag = true; } else if (maze[x - 1][y] == 0) { maze[x - 1][y] = 2; path.push(new Point(x - 1, y)); flag = true; } else if (maze[x][y - 1] == 0) { maze[x][y - 1] = 2; path.push(new Point(x, y - 1)); flag = true; } /* * 如果四周都没有通路则将点从路径中删除,即弹出栈顶元素。 * 如果此时栈为空,则表明弹出的是入口点,即此迷宫无解。 * 否则后退一个点重新探测。 */ if (flag == false) { start = path.pop(); if (path.empty()) { System.out.println("此迷宫没有通路。"); break; } } /* * 读取栈顶元素并判断其是否是出口。 */ Point peek = path.peek(); if ((peek.x == end.x) && (peek.y == end.y)) { System.out.println("此迷宫具有通路:" + path); break; } /* * 如果栈顶元素不是出口,则以该元素为起点继续进行探测。 */ start = peek; x = start.x; y = start.y; } while (!path.empty()); }

推荐:数据结构:栈应用_求解迷宫问题3

/************************************************************************/ /* 数据结构:栈应用:求解迷宫问题                                          

一个迷宫可以用如下的二维矩阵来表示 其中,1表示“墙壁”(红色部分) 0表示“通路”白色部分 黄色的单元格分别表示迷宫的入口和出口,用二维矩阵来表示则为: { {1, 1, 1, 1, 1, 1, 1, 1, 1,

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。