阿波罗与戴安娜迷宫BFS算法异常终止问题求助

看起来你在阿波罗与戴安娜迷宫的BFS实现里卡壳了——初始节点的邻居能进队列，但后续节点的邻居死活加不进去，算法跑3次就停了。结合你给出的代码片段，梳理几个最可能踩的坑：

1. 访问标记的时机完全错了 #

这是BFS新手最常犯的错误：你大概率是在弹出节点时才标记已访问，而不是在把节点推进队列的瞬间就标记。

举个反例，如果你的代码是这样：

current = NodeQueue.front();
NodeQueue.pop();
current.visited = true; // 弹出后才标记

那问题就大了：同一个节点可能被多次推进队列，而且当你处理后续节点的邻居时，原矩阵里的节点还是未访问状态，要么重复入队导致逻辑混乱，要么你的邻居判断逻辑会错误跳过合法节点。

正确的做法是：在push节点到队列前，立刻标记原矩阵里的对应节点为已访问，比如：

Node& startNode = NodeMatrix[0][0];
startNode.visited = true;
NodeQueue.push(startNode);

2. 邻居遍历的边界/可通行判断有问题 #

你在找当前节点的邻居（比如迷宫的上下左右格子）时，可能没正确处理边界，或者把障碍当成了可通行路径：

• 比如没判断newRow >= 0或者newCol < maxCol，导致越界访问，程序悄悄跳过了这些邻居；
• 或者阿波罗与戴安娜迷宫里的障碍判断逻辑错了，比如把应该通行的格子当成了墙，导致没有新节点入队。

建议补全邻居遍历的逻辑，参考这个模板：

// 定义四个移动方向：上、下、左、右
int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
for (auto& dir : dirs) {
    int newRow = current.row + dir[0];
    int newCol = current.col + dir[1];
    // 三重判断：不越界 + 未被访问 + 是可通行格子
    if (newRow >= 0 && newRow < maxRow && newCol >=0 && newCol < maxCol
        && !NodeMatrix[newRow][newCol].visited
        && NodeMatrix[newRow][newCol].isPassable) {
        // 标记后再入队
        NodeMatrix[newRow][newCol].visited = true;
        NodeQueue.push(NodeMatrix[newRow][newCol]);
    }
}

3. 节点拷贝导致状态不同步 #

看你的代码片段，你是把NodeMatrix[0][0]直接push进队列，然后弹出时赋值给current——如果Node是值类型，那current只是原节点的一个拷贝而已！

这意味着你修改current.visited的时候，根本不会影响NodeMatrix里的原节点。后续处理其他节点时，原节点还是未访问状态，你的邻居判断自然会出问题，甚至根本找不到新的可入队节点。

解决方法二选一：

• 改用指针队列：queue<Node*>，这样队列里存的是原节点的地址，修改时直接操作矩阵里的节点；
• 不要修改拷贝的current，所有状态修改直接操作NodeMatrix里的对应节点。

4. 提前触发了终止条件 #

你的代码里if( !current.v...看起来是在判断当前节点是不是目标？如果这里面写了return或者break，可能误触发了终止逻辑，导致算法提前退出。比如目标节点刚好是初始节点的第二个邻居，处理完就直接停了，自然不会继续迭代。

快速排查步骤 #

1. 先检查访问标记的时机，确保入队时就标记原节点；
2. 加个打印日志，输出每次入队的节点坐标，看看哪些节点没被加进去；
3. 验证邻居遍历的逻辑，手动走一遍初始节点后的第二个节点，看它的邻居是否符合预期。

内容的提问来源于stack exchange，提问作者moose0306