米诺陶迷宫寻找最短路径c++代码

米诺陶迷宫寻路通常涉及使用算法如深度优先搜索（DFS）或广度优先搜索（BFS），特别是当它结合了A*搜索算法时，可以更高效地找到最短路径。这里是一个简单的C++代码片段，使用邻接矩阵表示迷宫：

#include <vector>
#include <queue>

struct Node {
    int x, y;
    int dist; // 到起点的距离
};

bool is_valid(int x, int y, const std::vector<std::vector<char>>& maze) {
    return x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] != '#';
}

Node* bfs(const std::vector<std::vector<char>>& maze, int startX, int startY, int endX, int endY) {
    std::vector<Node> nodes(maze.size() * maze[0].size(), {0, 0, -1});
    std::queue<Node*> q;
    nodes[startX * maze[0].size() + startY] = {startX, startY, 0};
    
    while (!q.empty()) {
        Node* node = q.front();
        q.pop();

        if (node->x == endX && node->y == endY)
            return node;

        for (int dx = -1; dx <= 1; dx++)
            for (int dy = -1; dy <= 1; dy++) {
                int newX = node->x + dx;
                int newY = node->y + dy;
                
                if (is_valid(newX, newY, maze)) {
                    if (nodes[newX * maze[0].size() + newY].dist == -1 || nodes[newX * maze[0].size() + newY].dist > node->dist + 1) {
                        nodes[newX * maze[0].size() + newY] = {newX, newY, node->dist + 1};
                        q.push(&nodes[newX * maze[0].size() + newY]);
                    }
                }
            }
    }

    return nullptr; // 没有找到路径
}