C++ 利用栈求解唯一路径迷宫：从起点 (1,1) 到终点 (m - 2,n - 2)

好的，下面是一个使用栈来解决迷宫问题的 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"。 这个程序假设迷宫的最外圈全是障碍物，并且路径是唯一的。希望这能帮到你！如果有任何问题，请随时提问。 ######[AI写代码神器 | 732点数解答 | 2024-11-03 02:34:53]