C++ 迷宫求解：非递归算法实现及最短路径寻找

{'title':'C++ 迷宫求解：非递归算法实现及最短路径寻找','description':'使用 C++ 实现一个迷宫求解程序，利用栈和队列数据结构分别实现非递归算法和广度优先搜索算法，找到迷宫中的一条通路或所有通路，并输出最短路径。','keywords':'迷宫, 算法, C++, 栈, 队列, 非递归, 广度优先搜索, 最短路径, 通路','content':'## 迷宫求解程序设计\n\n问题描述：以一个 m×n 的长方阵表示迷宫，0 和1分别表示迷宫中的通路和障碍。利用C++设计一个程序,对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。\n\n功能要求：\n1.以链表作存储结构的栈类型，编写一个求解迷宫的非递归程序。求得的通路以 (i，j) 的形式按通路顺序输出，其中(i，j) 为迷宫中的一个坐标。\n2.求得迷宫中所有可能的通路，并输出最短路径。\n\n实验报告内容：\n1. 描述程序中所用的算法及其对应的主要思想。\n2. 说明迷宫中是否有通路，求得迷宫中所有可能的通路。\n3. 输出迷宫通路最短通路路径\n\n算法描述：\n\n1. 非递归算法\n\n* 算法思想：利用栈数据结构，模拟递归过程，实现对迷宫的深度优先搜索。\n* 算法步骤：\n 1. 定义一个栈，用来存储迷宫的通路坐标。\n 2. 从迷宫的入口开始，将入口坐标入栈。\n 3. 循环执行以下步骤：\n 1）若栈为空，则迷宫中没有通路，结束循环。\n 2）取出栈顶元素，记为当前坐标。\n 3）若当前坐标为出口，则找到了通路，结束循环。\n 4）判断当前坐标的上、下、左、右四个相邻坐标的情况：\n - 若相邻坐标为通路且未访问过，则将其入栈，并标记为已访问。\n 5）若四个相邻坐标均不满足条件，则将当前坐标出栈。\n 4. 若找到了通路，则将栈中的坐标按顺序输出即可。\n\n2. 最短路径算法\n\n* 算法思想：利用广度优先搜索算法，从入口开始，逐层搜索迷宫中的通路，直到找到出口。在搜索的过程中，用队列保存每一条路径，保证先搜索到的路径一定是最短的。当找到出口时，即可输出最短路径。\n* 算法步骤：\n 1. 定义一个队列，用来存储迷宫的通路路径。\n 2. 从迷宫的入口开始，将入口坐标入队列。\n 3. 循环执行以下步骤：\n 1）若队列为空，则迷宫中没有通路，结束循环。\n 2）取出队首元素，记为当前路径。\n 3）判断当前路径的最后一个坐标是否为出口：\n - 若是，则找到了一条通路，结束循环。\n 4）判断当前路径的最后一个坐标的上、下、左、右四个相邻坐标的情况：\n - 若相邻坐标为通路且未访问过，则将其加入当前路径，并标记为已访问。\n 5）将当前路径的所有相邻坐标入队列。\n 4. 若找到了通路，则输出该通路路径。\n\n实验结果：\n1. 若迷宫中存在通路，则输出一条通路的坐标序列。\n2. 若迷宫中不存在通路，则输出无通路的结论。\n3. 若迷宫中存在多条通路，则输出最短路径的坐标序列。\n\n代码实现：\ncpp\n// 代码示例\n#include <iostream>\n#include <queue>\n#include <stack>\nusing namespace std;\n\n// 迷宫地图\nconst int MAX_ROW = 10; // 最大行数\nconst int MAX_COL = 10; // 最大列数\nint maze[MAX_ROW][MAX_COL]; // 迷宫地图，0 表示通路，1 表示障碍\n\n// 存储迷宫坐标结构\nstruct Coord {\n int row; // 行坐标\n int col; // 列坐标\n};\n\n// 判断坐标是否合法\nbool isValidCoord(int row, int col) {\n return row >= 0 && row < MAX_ROW && col >= 0 && col < MAX_COL;\n}\n\n// 非递归算法求解迷宫\nbool solveMazeNonRecursive(Coord start, Coord end) {\n stack<Coord> path; // 存储路径的栈\n // 初始化起点\n path.push(start);\n // 标记起点已访问\n maze[start.row][start.col] = 2;\n while (!path.empty()) {\n Coord cur = path.top(); // 获取栈顶元素\n path.pop(); // 出栈\n if (cur.row == end.row && cur.col == end.col) { // 到达终点\n cout << \'路径：\' << endl;\n while (!path.empty()) {\n Coord temp = path.top();\n cout << \'(\', temp.row, \',\', temp.col, \'\', \' << endl;\n path.pop();\n }\n cout << \'(\', cur.row, \',\', cur.col, \'\', \' << endl;\n return true;\n }\n // 尝试四个方向\n Coord nextCoord;\n nextCoord.row = cur.row - 1; // 向上\n nextCoord.col = cur.col;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 上方为通路\n path.push(nextCoord); // 入栈\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n continue;\n }\n nextCoord.row = cur.row + 1; // 向下\n nextCoord.col = cur.col;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 下方为通路\n path.push(nextCoord); // 入栈\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n continue;\n }\n nextCoord.row = cur.row; // 向左\n nextCoord.col = cur.col - 1;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 左方为通路\n path.push(nextCoord); // 入栈\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n continue;\n }\n nextCoord.row = cur.row; // 向右\n nextCoord.col = cur.col + 1;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 右方为通路\n path.push(nextCoord); // 入栈\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n continue;\n }\n }\n return false; // 没有找到通路\n}\n\n// 广度优先搜索算法求解迷宫最短路径\nbool solveMazeBFS(Coord start, Coord end) {\n queue<vector<Coord>> paths; // 存储路径的队列\n vector<Coord> path; // 当前路径\n path.push_back(start); // 初始化起点\n paths.push(path); // 将起点路径入队列\n // 标记起点已访问\n maze[start.row][start.col] = 2;\n while (!paths.empty()) {\n vector<Coord> curPath = paths.front(); // 获取队首元素\n paths.pop(); // 出队列\n Coord lastCoord = curPath.back(); // 获取当前路径的最后一个坐标\n if (lastCoord.row == end.row && lastCoord.col == end.col) { // 到达终点\n cout << \'最短路径：\' << endl;\n for (auto& coord : curPath) {\n cout << \'(\', coord.row, \',\', coord.col, \'\', \' << endl;\n }\n return true;\n }\n // 尝试四个方向\n Coord nextCoord;\n nextCoord.row = lastCoord.row - 1; // 向上\n nextCoord.col = lastCoord.col;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 上方为通路\n vector<Coord> newPath = curPath; // 复制当前路径\n newPath.push_back(nextCoord); // 添加新坐标\n paths.push(newPath); // 将新路径入队列\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n }\n nextCoord.row = lastCoord.row + 1; // 向下\n nextCoord.col = lastCoord.col;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 下方为通路\n vector<Coord> newPath = curPath; // 复制当前路径\n newPath.push_back(nextCoord); // 添加新坐标\n paths.push(newPath); // 将新路径入队列\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n }\n nextCoord.row = lastCoord.row; // 向左\n nextCoord.col = lastCoord.col - 1;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 左方为通路\n vector<Coord> newPath = curPath; // 复制当前路径\n newPath.push_back(nextCoord); // 添加新坐标\n paths.push(newPath); // 将新路径入队列\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n }\n nextCoord.row = lastCoord.row; // 向右\n nextCoord.col = lastCoord.col + 1;\n if (isValidCoord(nextCoord.row, nextCoord.col) && maze[nextCoord.row][nextCoord.col] == 0) { // 右方为通路\n vector<Coord> newPath = curPath; // 复制当前路径\n newPath.push_back(nextCoord); // 添加新坐标\n paths.push(newPath); // 将新路径入队列\n maze[nextCoord.row][nextCoord.col] = 2; // 标记已访问\n }\n }\n return false; // 没有找到通路\n}\n\nint main() {\n // 初始化迷宫地图\n maze[0][0] = 0; maze[0][1] = 0; maze[0][2] = 0; maze[0][3] = 1; maze[0][4] = 1; maze[0][5] = 1; maze[0][6] = 1; maze[0][7] = 1; maze[0][8] = 1; maze[0][9] = 1;\n maze[1][0] = 1; maze[1][1] = 0; maze[1][2] = 0; maze[1][3] = 1; maze[1][4] = 0; maze[1][5] = 0; maze[1][6] = 0; maze[1][7] = 1; maze[1][8] = 0; maze[1][9] = 1;\n maze[2][0] = 1; maze[2][1] = 1; maze[2][2] = 0; maze[2][3] = 1; maze[2][4] = 0; maze[2][5] = 1; maze[2][6] = 0; maze[2][7] = 1; maze[2][8] = 0; maze[2][9] = 1;\n maze[3][0] = 1; maze[3][1] = 1; maze[3][2] = 0; maze[3][3] = 1; maze[3][4] = 0; maze[3][5] = 0; maze[3][6] = 0; maze[3][7] = 1; maze[3][8] = 1; maze[3][9] = 1;\n maze[4][0] = 1; maze[4][1] = 1; maze[4][2] = 0; maze[4][3] = 1; maze[4][4] = 1; maze[4][5] = 1; maze[4][6] = 1; maze[4][7] = 1; maze[4][8] = 1; maze[4][9] = 1;\n maze[5][0] = 1; maze[5][1] = 1; maze[5][2] = 0; maze[5][3] = 1; maze[5][4] = 1; maze[5][5] = 1; maze[5][6] = 1; maze[5][7] = 1; maze[5][8] = 0; maze[5][9] = 1;\n maze[6][0] = 1; maze[6][1] = 0; maze[6][2] = 0; maze[6][3] = 0; maze[6][4] = 0; maze[6][5] = 0; maze[6][6] = 0; maze[6][7] = 0; maze[6][8] = 0; maze[6][9] = 1;\n maze[7][0] = 1; maze[7][1] = 0; maze[7][2] = 1; maze[7][3] = 1; maze[7][4] = 1; maze[7][5] = 1; maze[7][6] = 1; maze[7][7] = 1; maze[7][8] = 1; maze[7][9] = 1;\n maze[8][0] = 1; maze[8][1] = 0; maze[8][2] = 1; maze[8][3] = 1; maze[8][4] = 1; maze[8][5] = 1; maze[8][6] = 1; maze[8][7] = 1; maze[8][8] = 1; maze[8][9] = 1;\n maze[9][0] = 1; maze[9][1] = 0; maze[9][2] = 1; maze[9][3] = 1; maze[9][4] = 1; maze[9][5] = 1; maze[9][6] = 1; maze[9][7] = 1; maze[9][8] = 1; maze[9][9] = 1;\n\n // 定义起点和终点\n Coord start = {0, 0}; // 起点\n Coord end = {6, 6}; // 终点\n\n // 非递归算法求解迷宫\n if (solveMazeNonRecursive(start, end)) {\n cout << \'非递归算法找到通路！\' << endl;\n } else {\n cout << \'非递归算法没有找到通路！\' << endl;\n }\n\n // 广度优先搜索算法求解迷宫最短路径\n if (solveMazeBFS(start, end)) {\n cout << \'广度优先搜索算法找到最短路径！\' << endl;\n } else {\n cout << \'广度优先搜索算法没有找到通路！\' << endl;\n }\n\n return 0;\n}\n\n',