数据结构迷宫求解c++

在C++中，数据结构迷宫求解通常涉及图论算法，特别是深度优先搜索（DFS）或广度优先搜索（BFS）。这两种方法常用于解决迷宫问题，因为迷宫可以看作是一个二维网格，每个格子代表一个节点，而相邻的格子之间有边相连。

1. **深度优先搜索（DFS）**：从起点开始，沿着一条路径尽可能深地搜索，直到无法继续为止，然后回溯寻找其他路径。可以用递归或栈来实现。

void dfs(int x, int y, vector<vector<char>>& maze, bool& visited) {
    // 检查边界和墙壁
    if (x < 0 || y < 0 || x >= maze.size() || y >= maze[0].size() || maze[x][y] == 'X')
        return;
    
    visited[x][y] = true; // 标记当前位置已访问
    
    // 探索相邻位置
    dfs(x + 1, y, maze, visited); // 右
    dfs(x - 1, y, maze, visited); // 左
    dfs(x, y + 1, maze, visited); // 下
    dfs(x, y - 1, maze, visited); // 上
}

2. **广度优先搜索（BFS）**：则是先访问所有邻居，再访问他们的邻居，直到找到出口。这里通常使用队列来存储待探索的位置。

queue<pair<int, int>> q;
q.push({start_x, start_y});

while (!q.empty()) {
    int x = q.front().first;
    int y = q.front().second;
    q.pop();
    
    // ... (处理当前位置)
    
    // 添加邻居到队列
    if (x + 1 < maze.size() && maze[x+1][y] != 'X') {
        q.push({x + 1, y});
    }
    // ...
}