c++求解迷宫最短路径

在C++中求解迷宫的最短路径通常可以使用Dijkstra算法或A*搜索算法。这里我们先简单介绍Dijkstra算法，它适用于所有边的权重都是非负的情况。

**Dijkstra算法步骤**:

1. **初始化**：设置起点为已知的“起始节点”，并将其距离设为0，其余节点的距离设为无穷大（通常是`INT_MAX`）。创建一个优先队列存放节点及其距离。

2. **贪心选择**：每次从优先队列中选取距离最小的未访问节点，这个节点称为当前“最短路径”的终点。

3. **更新邻接点**：对于该终点的所有相邻节点，如果通过终点到达它们的距离比它们当前的距离更短，则更新它们的距离，并将它们加入优先队列。

4. **重复直到终点**：如果队列为空，说明已经遍历完所有节点，找到最短路径；否则继续迭代直到找到目标节点或者队列为空。

5. **回溯路径**：当找到目标节点时，沿着距离值不断减小的方向回溯，记录下每一步的选择，得到最短路径。

**A*搜索**则在此基础上增加了启发式函数，利用对目标位置的预估距离来加速搜索，适用于大型、复杂迷宫。

**相关问题--:**
1. Dijkstra算法适合什么样的迷宫结构？
2. A*搜索是如何改进Dijkstra的？
3. 如何在C++中实现优先队列支持按距离排序？

相关问题

用队列求解迷宫最短路径问题，使用C++

在C++中，我们可以利用广度优先搜索（Breadth First Search, BFS）算法结合队列数据结构解决迷宫的最短路径问题。这里是一个基本的步骤：

1. **初始化**：
- 创建一个二维数组表示迷宫，其中0代表通路，非0值代表墙壁。
- 初始化起点（start）到所有节点的距离为无穷大，除了起点自身距离设为0。
- 创建一个队列存储待访问的节点，将起点放入队列。

2. **遍历**：
- 当队列非空时，循环执行以下操作：
- 取出队首的节点，如果该节点是终点，则找到了最短路径，返回路径长度。
- 如果节点不是终点，更新其相邻且未访问过的节点（上下左右），将它们的距离设置为当前节点的距离加一，并将它们加入队列。

3. **路径记录**：
- 每次从队列取出节点时，记得保存下一条路径，以便于回溯找到实际的路径序列。

4. **结束条件**：
- 如果队列为空并且没有找到终点，说明迷宫中不存在从起点到达终点的路径。

5. **实现**：
使用`std::queue`容器（如`std::queue<std::pair<int, int>>`）来存储节点位置，同时可以考虑用一个辅助的邻接表或二维数组来加速查找。

#include <iostream>
#include <queue>
using namespace std;

// 根据坐标检查是否越界
bool isValid(int row, int col, int mazeSize) {
    return row >= 0 && row < mazeSize && col >= 0 && col < mazeSize;
}

int bfs(int maze[mazeSize][mazeSize], int startRow, int startCol, int endRow, int endCol) {
    // 初始化距离数组
    vector<vector<int>> dist(mazeSize, vector<int>(mazeSize, INT_MAX));
    dist[startRow][startCol] = 0;

    queue<pair<int, int>> q;
    q.push({startRow, startCol});

    while (!q.empty()) {
        auto [row, col] = q.front();
        q.pop();

        if (row == endRow && col == endCol)
            return dist[row][col]; // 找到了目标点

        for (auto [dx, dy] : {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
            int newRow = row + dx, newCol = col + dy;
            if (isValid(newRow, newCol, mazeSize) && maze[newRow][newCol] == 0 && dist[newRow][newCol] > dist[row][col] + 1) {
                dist[newRow][newCol] = dist[row][col] + 1;
                q.push({newRow, newCol});
            }
        }
    }

    return -1; // 无解
}

int main() {
    int maze[] = {
        // 迷宫地图的示例
        // ...省略...
    };
    
    int start = 0, end = find_end(maze); // 找到起点和终点
    cout << "Shortest path length is: " << bfs(maze, start, start, end, end) << endl;
    return 0;
}

用栈求解迷宫最短路径问题，使用C++

栈是一种先进后出（LIFO）的数据结构，非常适合用于解决迷宫问题中的最短路径搜索，特别是当路径需要回溯时。一种常见的算法是宽度优先搜索（Breadth-First Search, BFS），也可以通过广度优先的方式利用栈来实现。

以下是使用C++实现基本版的宽度优先搜索迷宫解决方案的步骤：

#include <vector>
#include <queue>
using namespace std;

// 定义迷宫的结构体（假设每个格子有0表示空地，1表示障碍）
struct Cell {
    bool visited;
    int distance; // 到起点的距离
};

class MazeSolver {
private:
    vector<vector<Cell>> maze;
    int start, end; // 起点和终点

public:
    MazeSolver(vector<vector<int>>& maze, int start, int end) : maze(maze), start(start), end(end) {}

    // 使用深度优先搜索，辅助函数
    void dfs(int x, int y, int dist) {
        if (x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1)
            return;

        maze[x][y].distance = dist;
        maze[x][y].visited = true;

        if (x == end) {
            cout << "Shortest path found: " << dist << endl;
            return;
        }

        // 邻居探索
        queue<pair<int, int>> neighbors;
        neighbors.push({x+1, y}); // 上
        neighbors.push({x-1, y}); // 下
        neighbors.push({x, y+1}); // 右
        neighbors.push({x, y-1}); // 左

        while (!neighbors.empty()) {
            auto [nx, ny] = neighbors.front();
            neighbors.pop();

            if (!maze[nx][ny].visited)
                dfs(nx, ny, dist + 1);
        }
    }

    // 主函数，开始搜索
    void bfs() {
        maze[start][start].distance = 0;
        maze[start][start].visited = true;
        queue<pair<int, int>> q;
        q.push({start, start});

        while (!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();

            for (auto [dx, dy] : {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
                int nx = x + dx, ny = y + dy;
                if (isValid(nx, ny)) {
                    maze[nx][ny].distance = maze[x][y].distance + 1;
                    maze[nx][ny].visited = true;
                    q.push({nx, ny});
                }
            }
        }
    }

private:
    // 检查是否越界或者碰到墙壁
    bool isValid(int x, int y) {
        return x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] != 1;
    }
};

int main() {
    // 初始化迷宫矩阵和起始点、结束点...
    vector<vector<int>> maze = ...;
    int start = ...;
    int end = ...;
    
    MazeSolver solver(maze, start, end);
    solver.bfs(); // 开始搜索
    return 0;
}