求解迷宫从入口到出口的路径c++

在C++中，求解迷宫从入口到出口的路径通常可以使用深度优先搜索（Depth First Search, DFS）或广度优先搜索（Breadth First Search, BFS）算法。这里以DFS为例进行说明：

**DFS方法：**
1. 定义一个二维数组表示迷宫，其中0代表空地，1代表墙壁。
2. 创建一个函数`dfs(int x, int y, vector<vector<int>>& maze)`，x,y为当前位置，maze是迷宫数组。
3. 首先检查当前位置是否合法（在迷宫范围内且不是墙壁），然后标记当前位置为已访问（如maze[x][y] = -1）。
4. 如果当前位置是出口，则返回true，表示找到了路径；否则，尝试将相邻的未访问位置作为新起点进行递归调用。
5. 当所有邻接位置都检查过后，回溯并继续搜索其他方向。

bool dfs(int x, int y, vector<vector<int>>& maze) {
    // ... (检查边界、合法性等)
    if (x == exit_x && y == exit_y) return true; // 找到出口

    for (int dx[] = {0, 0, -1, 1}; int i = 0; i < 4) {
        int nx = x + dx[i], ny = y + dy[i];
        if (isValid(nx, ny, maze)) {
            maze[nx][ny] = -1; // 标记为已访问
            if (dfs(nx, ny, maze)) return true;
            maze[nx][ny] = 0; // 回溯，恢复路径
        }
    }
    return false;
}

**BFS方法：**
1. 使用队列进行广度优先遍历，首先将起始位置放入队列。
2. 循环直到队列为空，每次取出队首元素，检查其是否为出口。如果不是，将其未访问的邻居加入队列，并标记为已访问。
3. 重复步骤2直到找到出口。

这两种方法都需要在开始搜索前设置好初始状态（例如入口为已知坐标，出口位置已知）。