一个 5×6 的迷宫样例如下： 要求给出从起点（1，1）到终点（3，4）的路径。 为了处理方便，保证最外圈全都为障碍物。 扩展到一般情况，一个 m×n 的迷宫，要求输出从起点（1，1）到终点（m-2，n-2）的路径。 测试实例保证路径是唯一的。 该题要求自行设计一个栈来做。如果设计的是顺序栈，则保证栈的大小不超过 200 个元素。 输入 第一行为两个整数 m 和 n，表示 m×n 的迷宫。 接下来有 m 行，每行有 n 个数（n 个数之间用空格间隔，值 = 0 表示可以通行，值 = 1 表示为障碍物） 输出 输出从起点到终点的路径，每个坐标占一行，坐标间的行号和列号用一个空格间隔。具体格式可参考样例。c++ 源代码

好的，下面是一个使用栈来解决迷宫问题的 C++ 程序。这个程序会读取迷宫的大小和内容，并找到从起点 (1, 1) 到终点 (m-2, n-2) 的路径。 ```cpp #include <iostream> #include <vector> #include <stack> using namespace std; struct Point { int x, y; }; const int MAX_SIZE = 200; const int dx[4] = {0, 1, 0, -1}; const int dy[4] = {1, 0, -1, 0}; bool isValid(int x, int y, int m, int n, vector<vector<int>>& maze) { return x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0; } void printPath(stack<Point>& path) { while (!path.empty()) { cout << path.top().x + 1 << " " << path.top().y + 1 << endl; path.pop(); } } int main() { int m, n; cin >> m >> n; vector<vector<int>> maze(m, vector<int>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { cin >> maze[i][j]; } } stack<Point> path; vector<vector<bool>> visited(m, vector<bool>(n, false)); path.push({0, 0}); visited[0][0] = true; while (!path.empty()) { Point current = path.top(); if (current.x == m - 3 && current.y == n - 3) { printPath(path); return 0; } bool found = false; for (int i = 0; i < 4; ++i) { int newX = current.x + dx[i]; int newY = current.y + dy[i]; if (isValid(newX, newY, m, n, maze) && !visited[newX][newY]) { path.push({newX, newY}); visited[newX][newY] = true; found = true; break; } } if (!found) { path.pop(); } } cout << "No path found" << endl; return 0; } ``` 解释 1. Point 结构体：用于存储迷宫中的点。 2. isValid 函数：检查一个点是否在迷宫内且不是障碍物。 3. printPath 函数：打印从栈中弹出的路径。 4. 主函数： - 读取迷宫的大小 `m` 和 `n`。 - 读取迷宫的内容。 - 初始化栈和访问数组。 - 将起点 (0, 0) 压入栈并标记为已访问。 - 使用深度优先搜索（DFS）遍历迷宫，直到找到终点或栈为空。 - 如果找到终点，调用 `printPath` 函数打印路径。 - 如果没有找到路径，输出 "No path found"。 这个程序假设迷宫的最外圈全是障碍物，并且路径是唯一的。希望这能帮到你！如果有任何问题，请随时提问。 [2024-11-03 02:34:53 | AI写代码神器 | 732点数解答]