C++迷宫问题完全详解
2023-12-20 15:04:51
一、提出问题
迷宫我们都玩过,有些复杂的看的眼花缭乱,但是有没有想过,让机器帮你完成这个工作,想着就很酷,好,废话不多说
,直接开干!!!
二、寻找解决方法
解决迷宫问题可以有多种算法,这里介绍深度优先搜索跟广度优先算法。
深度优先搜索(DFS)和广度优先搜索(BFS)是两种常用的图遍历算法,适用于不同的问题和场景。下面我将对它们进行解释,并介绍它们的适用场景以及优缺点。
深度优先搜索(DFS):
- 深度优先搜索从起始节点开始,沿着一条路径尽可能深入地访问节点,直到无法继续或者达到目标节点为止。
- 在每个节点上,DFS首先探索一个子节点,然后再探索另一个子节点,以此类推,直到所有可能的路径都被探索完毕。
- DFS使用栈来保存需要进一步探索的节点,因此采用了后进先出(LIFO)的策略。
适用场景:
- 当问题的解决方案位于树或图的深处时,DFS通常更有效,因为它能够快速地向下搜索并深入解空间。
- 例如,在迷宫问题中,DFS可以通过在每个位置上依次探索四个方向的移动来搜索路径,直到找到终点或无法继续移动为止。
优点:
- 实现简单,只需使用递归或堆栈即可。
- 对于解决方案位于深处的问题,DFS通常比BFS更快。
缺点:
- 可能陷入无限循环,如果图中存在环路。
- 不保证找到最短路径,因为它首先遍历深度较大的节点。
广度优先搜索(BFS):
- 广度优先搜索从起始节点开始,逐层地访问相邻节点,直到找到目标节点或者遍历完整个图。
- 在每一层上,BFS首先访问当前节点的所有未访问邻居节点,然后再依次访问下一层的节点。
- BFS使用队列来保存需要进一步探索的节点,因此采用了先进先出(FIFO)的策略。
适用场景:
- 当问题的解决方案位于树或图的较浅部分时,BFS通常更有效,因为它可以快速地扩展到距离起始节点更远的节点。
- 例如,在查找最短路径的问题中,BFS可以找到从起点到终点的最短路径。
优点:
- 可以找到最短路径,因为它按层次遍历图。
- 对于解决方案位于较浅部分的问题,BFS通常比DFS更快。
缺点:
- 需要额外的空间来存储队列,可能占用较多的内存。
- 在搜索深度较大的图时,BFS可能会变得比较慢。
总结:
- DFS适用于解决方案位于深处的问题,并且不需要找到最短路径。
- BFS适用于解决方案位于较浅部分的问题,并且需要找到最短路径。
在实际应用中,根据问题的特点和需求,选择合适的算法来进行图遍历是非常重要的。
既然两种方法都能实现,那我就两个都实现了把,广度优先算法能找到最短路径,深度优先算法能尽快找出出口,各有优点。
三、深度优先查找
3.1 深度优先实现代码
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
struct Point {
int x;
int y;
Point(int x, int y) : x(x), y(y) {}
};
// 检查点是否在迷宫范围内
bool isValidPoint(const std::vector<std::vector<int>>& maze, int x, int y) {
int rows = maze.size();
int cols = maze[0].size();
return (x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 0);
}
// 解决迷宫问题-深度优先
bool solveMaze(std::vector<std::vector<int>>& maze, const Point& start, const Point& end) {
int rows = maze.size();
int cols = maze[0].size();
// 创建堆栈
std::stack<Point> stack;
stack.push(start);
// 创建标记矩阵,用于记录已访问的点
std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
visited[start.x][start.y] = true;
// 定义四个方向上的移动
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
while (!stack.empty()) {
Point current = stack.top();
// 如果当前点是终点,找到解决方案,返回真
if (current.x == end.x && current.y == end.y) {
// 标记路径上的位置为-1
while (!stack.empty()) {
Point point = stack.top();
maze[point.x][point.y] = -1;
stack.pop();
}
return true;
}
// 尝试四个方向上的移动
bool moved = false;
for (int i = 0; i < 4; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];
if (isValidPoint(maze, newX, newY) && !visited[newX][newY]) {
stack.push(Point(newX, newY));
visited[newX][newY] = true;
moved = true;
break;
}
}
// 如果无法移动到相邻点,则回溯到上一个点
if (!moved) {
stack.pop();
}
}
// 没有找到解决方案,返回假
return false;
}
// 打印迷宫图
void printMaze(const std::vector<std::vector<int>>& maze, const Point& start, const Point& end) {
int rows = maze.size();
int cols = maze[0].size();
// 输出上边框
for (int i = 0; i < cols + 2; i++) {
std::cout << "# ";
}
std::cout << std::endl;
// 输出迷宫内容
for (int i = 0; i < rows; i++) {
std::cout << "# "; // 左边框
for (int j = 0; j < cols; j++) {
if (i == start.x && j == start.y) {
std::cout << "S "; // 起点标记为"S"
}
else if (i == end.x && j == end.y) {
std::cout << "E "; // 终点标记为"E"
}
else if (maze[i][j] == 0) {
std::cout << " "; // 空路径
}
// 在路径上画线
else if (maze[i][j] == -1) {
std::cout << "x ";
}
else {
std::cout << "█ "; // 墙壁
}
}
std::cout << "#" << std::endl; // 右边框
}
// 输出下边框
for (int i = 0; i < cols + 2; i++) {
std::cout << "# ";
}
std::cout << std::endl;
}
int main() {
std::vector<std::vector<int>> maze = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
Point start(1, 1);
Point end(13, 13);
std::cout << "初始迷宫:" << std::endl;
printMaze(maze, start, end);
bool isSolvable = solveMaze(maze, start, end);
if (isSolvable) {
std::cout << "迷宫可以解决!" << std::endl;
}
else {
std::cout << "迷宫无解!" << std::endl;
}
std::cout << "解决后的迷宫:" << std::endl;
printMaze(maze, start, end);
while(1);
return 0;
}
3.1 输出结果:
S代表起始点,E代表终点,x代表路径
3.2 原理讲解
这里使用了栈,stack是一种先进后出(First In Last Out,FILO)的数据结构,它只有一个出口
栈中只有顶端的元素才可以被外界使用,因此栈不允许有遍历行为
栈中进入数据称为 — 入栈 push
栈中弹出数据称为 — 出栈 pop
生活中的栈:
深度优先搜索(DFS
):
- 创建一个堆栈,并将起点压入堆栈。
- 创建一个标记矩阵,并将起点标记为已访问。
- 循环直到堆栈为空:
4. 取出堆栈顶部的路径。
5. 获取该路径的最后一个点作为当前点。
6. 如果当前点是终点,则找到了解决方案,将路径上的点标记为解决路径。
7. 尝试当前点的四个相邻点:- 如果满足条件(在迷宫范围内且未被访问过),则创建新的路径并将新的点压入堆栈。
- 将相邻点标记为已访问。
- 退出当前循环
- 如果堆栈为空仍未找到解决方案,则表示迷宫无解。
四、广度优先查找
4.1 广度优先实现代码
#include <iostream>
#include <queue>
#include <vector>
struct Point {
int x;
int y;
Point(int x, int y) : x(x), y(y) {}
};
// 检查点是否在迷宫范围内
bool isValidPoint(const std::vector<std::vector<int>>& maze, int x, int y) {
int rows = maze.size();
int cols = maze[0].size();
return (x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 0);
}
// 解决迷宫问题并返回最短路径
std::vector<Point> solveMaze(std::vector<std::vector<int>>& maze, const Point& start, const Point& end) {
int rows = maze.size();
int cols = maze[0].size();
// 创建队列
std::queue<std::vector<Point>> queue;
queue.push({ start });
// 创建标记矩阵,用于记录已访问的点
std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
visited[start.x][start.y] = true;
// 定义四个方向上的移动
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };
while (!queue.empty()) {
std::vector<Point> path = queue.front();
queue.pop();
Point current = path.back();
// 如果当前点是终点,找到解决方案,返回最短路径
if (current.x == end.x && current.y == end.y) {
return path;
}
// 尝试四个方向上的移动
for (int i = 0; i < 4; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];
if (isValidPoint(maze, newX, newY) && !visited[newX][newY]) {
std::vector<Point> newPath = path;
newPath.push_back(Point(newX, newY));
queue.push(newPath);
visited[newX][newY] = true;
}
}
}
// 没有找到解决方案,返回空路径表示无解
return {};
}
// 打印迷宫图
void printMaze(const std::vector<std::vector<int>>& maze, const Point& start, const Point& end) {
int rows = maze.size();
int cols = maze[0].size();
// 输出上边框
for (int i = 0; i < cols + 2; i++) {
std::cout << "# ";
}
std::cout << std::endl;
// 输出迷宫内容
for (int i = 0; i < rows; i++) {
std::cout << "# "; // 左边框
for (int j = 0; j < cols; j++) {
if (i == start.x && j == start.y) {
std::cout << "S "; // 起点标记为"S"
}
else if (i == end.x && j == end.y) {
std::cout << "E "; // 终点标记为"E"
}
else if (maze[i][j] == 0) {
std::cout << " "; // 空路径
}
else if (maze[i][j] == -1) {
std::cout << "x "; // 解决路径上的位置用"x"表示
}
else {
std::cout << "█ "; // 墙壁
}
}
std::cout << "#" << std::endl; // 右边框
}
// 输出下边框
for (int i = 0; i < cols + 2; i++) {
std::cout << "# ";
}
std::cout << std::endl;
}
int main() {
std::vector<std::vector<int>> maze = {
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
{ 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1 },
{ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};
Point start(1, 1);
Point end(13, 13);
std::cout << "初始迷宫:" << std::endl;
printMaze(maze, start, end);
std::vector<Point> shortestPath = solveMaze(maze, start, end);
if (!shortestPath.empty()) {
std::cout << "迷宫可以解决!最短路径长度为:" << shortestPath.size() - 1 << std::endl;
// 标记解决路径上的位置
for (const auto& point : shortestPath) {
maze[point.x][point.y] = -1;
}
}
else {
std::cout << "迷宫无解!" << std::endl;
}
std::cout << "解决后的迷宫:" << std::endl;
printMaze(maze, start, end);
while (1);
return 0;
}
4.2 输出结果
4.3 算法讲解
广度优先使用的是Queue队列,队列是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口
队列容器允许从一端新增元素,从另一端移除元素
队列中只有队头和队尾才可以被外界使用,因此队列不允许有遍历行为
队列中进数据称为 — 入队 push
队列中出数据称为 — 出队 pop
生活中的队列:
广度优先搜索(BFS):
- 创建一个队列,并将起点加入队列。
- 创建一个标记矩阵,并将起点标记为已访问。
- 循环直到队列为空:
4. 从队列中取出一个路径。
5. 获取该路径的最后一个点作为当前点。
6. 如果当前点是终点,则找到了解决方案,返回该路径。
7. 尝试当前点的四个相邻点:- 如果满足条件(在迷宫范围内且未被访问过),则创建新的路径并将新的点添加到路径中。
- 将新的路径加入队列,并将相邻点标记为已访问。
- 如果队列为空仍未找到解决方案,则表示迷宫无解。
文章来源:https://blog.csdn.net/weixin_42163707/article/details/135105266
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!