C++ 深度优先搜索：求解 m×n 迷宫从 (1, 1) 到 (m - 2, n - 2) 的唯一路径

为了实现从起点 (1, 1) 到终点 (m-2, n-2) 的路径搜索，我们可以使用深度优先搜索 (DFS) 算法，并且使用栈来存储路径。以下是一个完整的 C++ 实现： ```cpp #include <iostream> #include <vector> #include <stack> using namespace std; // 定义方向数组，用于上下左右四个方向的移动 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 dfs(int m, int n, vector<vector<int>>& maze, stack<pair<int, int>>& path) { vector<vector<bool>> visited(m, vector<bool>(n, false)); stack<pair<int, int>> s; s.push({1, 1}); visited[1][1] = true; while (!s.empty()) { pair<int, int> current = s.top(); int x = current.first, y = current.second; if (x == m - 2 && y == n - 2) { // 找到终点，记录路径 while (!s.empty()) { path.push(s.top()); s.pop(); } return; } bool isDeadEnd = true; for (int i = 0; i < 4; ++i) { int newX = x + dx[i]; int newY = y + dy[i]; if (isValid(newX, newY, m, n, maze) && !visited[newX][newY]) { s.push({newX, newY}); visited[newX][newY] = true; isDeadEnd = false; break; } } if (isDeadEnd) { s.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<pair<int, int>> path; dfs(m, n, maze, path); while (!path.empty()) { cout << path.top().first << " " << path.top().second << endl; path.pop(); } return 0; } ``` 代码解释 1. 方向数组：`dx` 和 `dy` 用于表示四个方向（右、下、左、上）的移动。 2. 有效性检查：`isValid` 函数检查给定的坐标是否在迷宫范围内且不是障碍物。 3. 深度优先搜索 (DFS)： - 使用一个栈 `s` 来存储当前路径。 - 使用一个二维布尔数组 `visited` 来记录已经访问过的节点。 - 从起点 (1, 1) 开始，将起点压入栈中并标记为已访问。 - 在栈不为空的情况下，取出栈顶元素作为当前节点。 - 如果当前节点是终点 (m-2, n-2)，则记录路径并返回。 - 否则，尝试向四个方向移动，如果新位置有效且未访问过，则将其压入栈中并标记为已访问。 - 如果当前节点是死胡同（即四个方向都无法移动），则回溯（弹出栈顶元素）。 4. 主函数： - 读取迷宫的尺寸和内容。 - 调用 `dfs` 函数进行路径搜索。 - 输出路径。 这个实现确保了路径是唯一的，并且使用栈来存储路径，符合题目要求。 ######[AI写代码神器 | 864点数解答 | 2024-11-03 11:37:50]