迷宫路由游戏c++深度优先算法 广度优先算法

在C++中，解决迷宫路线问题可以使用深度优先搜索（Depth First Search, DFS）或广度优先搜索（Breadth First Search, BFS）。这里分别给出这两种算法的基本思路：

### 深度优先搜索（DFS）

#include <vector>
using namespace std;

bool isValid(vector<vector<int>>& maze, int x, int y) {
    return x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] == 0;
}

vector<int> dfs(vector<vector<int>>& maze, vector<int>& start, vector<int>& end) {
    vector<int> path = {start};
    vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size(), false));
    visited[start] = true;
    
    int x = start[0], y = start[1];
    while (!visited[end] && !maze[x][y]) {
        // 邻接节点检查
        if (x > 0 && isValid(maze, x - 1, y)) {
            path.push_back(x - 1);
            x--;
        }
        else if (x < maze.size() - 1 && isValid(maze, x + 1, y)) {
            path.push_back(x + 1);
            x++;
        }
        else if (y > 0 && isValid(maze, x, y - 1)) {
            path.push_back(y - 1);
            y--;
        }
        else if (y < maze[0].size() - 1 && isValid(maze, x, y + 1)) {
            path.push_back(y + 1);
            y++;
        }
    }
    
    if (visited[end]) {
        reverse(path.begin(), path.end());
        return path;
    } else {
        return {}; // 无解
    }
}

### 广度优先搜索（BFS）

#include <queue>
using namespace std;

vector<int> bfs(vector<vector<int>>& maze, vector<int>& start, vector<int>& end) {
    queue<pair<int, int>> q; // 起点
    q.push({start[0], start[1]});
    vector<vector<bool>> visited(maze.size(), vector<bool>(maze[0].size(), false));
    visited[start] = true;
    
    vector<int> path;
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        
        if (x == end[0] && y == end[1]) {
            path.push_back(end[0]);
            path.push_back(end[1]);
            break;
        }
        
        // 添加相邻节点到队列，同时标记为已访问
        if (isValid(maze, x, y - 1) && !visited[x][y - 1]) {
            q.push({x, y - 1});
            visited[x][y - 1] = true;
        }
        if (isValid(maze, x, y + 1) && !visited[x][y + 1]) {
            q.push({x, y + 1});
            visited[x][y + 1] = true;
        }
        if (isValid(maze, x - 1, y) && !visited[x - 1][y]) {
            q.push({x - 1, y});
            visited[x - 1][y] = true;
        }
        if (isValid(maze, x + 1, y) && !visited[x + 1][y]) {
            q.push({x + 1, y});
            visited[x + 1][y] = true;
        }
    }
    
    return path;
}

在上述代码中，`maze`是一个二维数组表示迷宫，`start`和`end`是起始和结束位置。DFS适合于找到一条从起点到终点的路径，而BFS则能保证找到最短路径。