C++深度优先迷宫生成算法，偶尔会生成出错误的迷宫

Question

迷宫实现代码如下，请重点关注showMaze函数和generate函数

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

class Maze {
    public:
        Maze(int row = 0, int col = 0);
        void connect(int i, int j);
        void disconnect(int i, int j);

        vector<int> connected(int i) const; // 修改为接收一个参数
        vector<int> surrounded(int i) const; // 修改为接收一个参数

        int Row() const;
        int Col() const;

        bool isConnected(int i, int j) const;

    private:
        int row;
        int col;
        vector<vector<int> > neighbor;
        vector<vector<int> > surround;
};

Maze::Maze(int row, int col) {
    this->row = row;
    this->col = col;

    for (int i = 0; i < col * row; i++) {
        vector<int> tmp(row * col, 0);
        neighbor.push_back(tmp);
        surround.push_back(tmp);
    }
    for (int i = 0; i < col * row; i++) {
        if ((i - 1) % col != 0)
            surround[i][i - 1] = 1; // 左邻居，排除第一列
        if ((i + 1) % col != 0)
            surround[i][i + 1] = 1; // 右邻居，排除最后一列
        if (i - col >= 0)
            surround[i][i - col] = 1; // 上邻居
        if (i + col < row * col)
            surround[i][i + col] = 1; // 下邻居
    }
}

void Maze::connect(int i, int j) {
    neighbor[i][j] = 1;
    neighbor[j][i] = 1;
}

void Maze::disconnect(int i, int j) {
    neighbor[i][j] = 0;
    neighbor[j][i] = 0;
}

vector<int> Maze::connected(int i) const { // 修正为单参数函数
    vector<int> result;
    for (int t = 0; t < row * col; t++) {
        if (neighbor[i][t] == 1) {
            result.push_back(t);
        }
    }
    return result;
}

vector<int> Maze::surrounded(int i) const { // 修正为单参数函数
    vector<int> result;
    for (int t = 0; t < row * col; t++) {
        if (surround[i][t] == 1) {
            result.push_back(t);
        }
    }
    return result;
}

int Maze::Row() const {
    return row;
}

int Maze::Col() const {
    return col;
}

bool Maze::isConnected(int i, int j) const {
    vector<int> con = this->connected(i);
    auto it = find(con.begin(), con.end(), j);
    if (it != con.end()) {
        return true;
    } else {
        return false;
    }
}

void showMaze(const Maze &m) {
    //自左上角向右下角显示
    int row = m.Row();
    int col = m.Col();

    for (int i = 0; i < col; i++) {
        cout << "_ ";
    }
    cout << endl;

    for (int r = 0; r < row; r++) {
        cout << "|";
        for (int c = 0; c < col; c++) {
            if (m.isConnected(r * col + c, (r + 1)* col + c)) {
                cout << " ";
            } else {
                cout << "_";
            }

            if (m.isConnected(r * col + c, r * col + c + 1)) {
                cout << " ";
            } else {
                cout << "|";
            }
        }
        cout << endl;
    }

}

namespace DFS {
    enum color {
        white,
        gray,
        black
    };

    Maze generate(int row, int col) {
        Maze result(row, col);
        vector<color> record(row * col, white);
        vector<int> current;
        current.reserve(static_cast<size_t>(row * col));

        record[0] = gray;
        current.push_back(0);
        
        while (current.size() != 0) {
            int index = current.back();
            vector<int> sur = result.surrounded(index);
            random_shuffle(sur.begin(), sur.end(), [](vector<int>::difference_type n)->vector<int>::difference_type{
                return rand() % n;
            });
            int i = 0;

            for (; i < sur.size(); i++) {
                if (record[sur[i]] == white) {
                    current.push_back(sur[i]);
                    result.connect(index, sur[i]);
                    record[sur[i]] = gray;
                    break;
                }
            }

            if (i == sur.size()) {
                current.pop_back();
                record[index] = black;
            }
        }

        return result;
    }
}

主函数如下

int main() {


    srand((unsigned int)time(NULL));


    Maze maze2 = DFS::generate(10, 10);
    showMaze(maze2);

    return 0;
}

大多情况都是这种对的

少数时候会有这样的，右侧第一列少了一堵墙，左侧给封死了

请关注一下generate中random_shuffle的第三个参数——用于随机的lambda，我觉得问题可能出在这里，如果没看出来问题的话，也请各位看看能不能给出别的随机写法，说不定就没问题了，谢谢！

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的代码中，迷宫生成算法基于深度优先搜索（DFS），并在 generate 函数中随机选择一个未访问过的相邻格子进行连接。从您的描述来看，问题可能出在随机性导致的边界条件处理不一致上。

首先，我注意到在 showMaze 函数中有两处判断相连情况的地方：

if (m.isConnected(r * col + c, (r + 1)* col + c)) { // 下方相连
    cout << " ";
} else {
    cout << "_";
}

if (m.isConnected(r * col + c, r * col + c + 1)) { // 右侧相连
    cout << " ";
} else {
    cout << "|";
}

对于您提到的问题，即右侧第一列少了一堵墙、左侧给封死了，这可能是由于在生成过程中没有正确处理边界条件，特别是在随机选取邻居时。目前的实现并没有排除某些非法移动（例如，在最右边一列时尝试向右移动）。

为了修复这个问题，我们可以在 generate 函数中的 for 循环内部添加对选定格子位置的检查，以确保不会尝试去连接超出迷宫边界的格子。请看修改后的 generate 函数部分：

 Maze generate(int row, int col) {
    Maze result(row, col);
    vector<color> record(row * col, white);
    vector<int> current;
    current.reserve(static_cast<size_t>(row * col));

    record[0] = gray;
    current.push_back(0);

    while (current.size() != 0) {
        int index = current.back();
        vector<int> sur = result.surrounded(index);
        
        // 过滤掉非法的邻居，防止超出边界
        sur.erase(remove_if(sur.begin(), sur.end(), [&](int n) {
            int x = n % col;
            int y = n / col;
            return (x == 0 && index % col == col - 1) || // 左侧已是最左边界，不应尝试向左连接
                   (y == 0 && index / col == row - 1) || // 上侧已是最上边界，不应尝试向上连接
                   (x == col - 1 && index % col == 0) || // 右侧已是最右边界，不应尝试向右连接
                   (y == row - 1 && index / col == 0);   // 下侧已是最下边界，不应尝试向下连接
        }), sur.end());

        random_shuffle(sur.begin(), sur.end());

        // ... 其他不变 ...
    }

    // ... 其他不变 ...
}

这个修改会确保在随机选择要连接的邻居时，不会尝试向已经超出迷宫范围的方向进行连接。这样应该能避免出现您所描述的那种错误的迷宫生成结果。