DFS迷宫生成算法异常求助：生成结果不符合预期

问题背景 #

尝试实现迷宫生成算法（自称DFS，但实际代码为BFS实现），但输出结果几乎全是墙壁，仅初始位置和个别位置有通路，不符合预期。

核心代码 #

// m_maze是m_dim*m_dim的矩阵，'#'代表墙壁，' '代表通路
// const int dxdy[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} }; // {上, 左, 下, 右}
void Maze::generate() {
std::queue<std::pair<int, int>>neighbours;
neighbours.emplace(0, 0);
m_maze[0][0] = ' '; // 标记为通路
while (!neighbours.empty()) {
    std::pair<int, int> currentCell = neighbours.front();

    for (int d = 0; d < 4; d++) {
        const int newX = currentCell.first + 2*dxdy[d][0];
        const int newY = currentCell.second + 2*dxdy[d][1];

        if (newX >= 0 && newY >= 0 && newX <= m_dim && newY <= m_dim && m_maze[newX][newY] && m_maze[newX][newY] == '#') {
            m_maze[currentCell.first + dxdy[d][0]][currentCell.second + dxdy[d][1]] = ' ';
            m_maze[newX][newY] = ' ';
            neighbours.emplace(newX, newY);
        }
    }

    neighbours.pop();
}
}

当前错误输出 #

#
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 # # # # # # # # # # # # #
 ##########################

调试建议及问题分析 #

1. 边界条件错误（核心问题） #

代码中newX <= m_dim && newY <= m_dim的边界判断完全错误：

• 若m_maze是m_dim*m_dim的矩阵，合法索引范围是0 <= x < m_dim和0 <= y < m_dim，使用<=会触发数组越界访问，导致未定义行为，无法正确识别目标单元格是否为墙壁。
• 修正方案：将边界判断改为newX < m_dim && newY < m_dim。

2. 冗余且危险的判断逻辑 #

if条件中的m_maze[newX][newY]属于冗余判断，且在越界时会非法访问内存。直接保留m_maze[newX][newY] == '#'即可，因为前面的边界判断已经确保索引合法。

3. 算法实现混淆（可选） #

你提到想用DFS生成迷宫，但当前代码用std::queue实现的是BFS。若需DFS，只需将std::queue替换为std::stack，并把neighbours.front()改为neighbours.top()，neighbours.pop()逻辑保持不变。

4. 验证方向数组 #

确认dxdy的方向定义与坐标系匹配：比如{0, -1}是否真的对应“上”，若矩阵行号从上到下递增，Y轴向下时该定义是正确的，可通过打印坐标值调试验证。

修正后的核心判断代码示例 #

if (newX >= 0 && newY >= 0 && newX < m_dim && newY < m_dim && m_maze[newX][newY] == '#') {
    m_maze[currentCell.first + dxdy[d][0]][currentCell.second + dxdy[d][1]] = ' ';
    m_maze[newX][newY] = ' ';
    neighbours.emplace(newX, newY);
}

内容的提问来源于stack exchange，提问作者Mr. Sir