以结构格式操作数据最终变得很奇怪

Question

所以我正在研究迷宫生成器程序作为 dfs 练习。

struct Point{
    Point *left,*right,*up,*down;
    int x,y;
    bool visited;
    Point(int n,int m)
        :x(n),y(m),visited(false),left(NULL),right(NULL),up(NULL),down(NULL)
    {}
};

并且我使用了一个for循环来初始化一个点向量的向量，每个都有一个唯一的地址和访问值分配为 false。

    vector<vector<Point*> > board;
        for(i=0;i<row;i++){
            for(j=0;j<col;j++){
                Point *temppt=new Point(j,i);
                tempv.push_back(temppt);
            }
            board.push_back(tempv);
        }
        for(i=0;i<row;i++){
            for(j=0;j<col;j++){
                if(i!=0)board[i][j]->up=board[i-1][j];
                if(i!=row-1)board[i][j]->down=board[i+1][j];
                if(j!=0)board[i][j]->left=board[i][j-1];
                if(j!=col-1)board[i][j]->right=board[i][j+1];
            }
        }

但是，当我在 dfs 搜索过程中操作它们时，发生了一些奇怪的事情...

每当我执行这段代码时

            board[now->y][now->x]->visited=true;

板向量 (board[x][0]) 的每个第一个值也都更改为 true，因为用这个 for 循环检查了它。

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                cout<<board[i][j]->visited;
            }
            cout<<endl;
        }

我应该怎么做才能逐个操作点而不是逐列操作

完整的 dfs 函数：

    void dfs(Point* now,Point* prev,int cnt){
        int dir,back;
        if(now->visited!=true){
            cnt++;
            if(prev!=NULL){
                if(prev->up==now){
                    hwall[now->x][now->y]=false;
                }
                else if(prev->down==now){
                    hwall[prev->x][prev->y]=false;
                }
                else if(prev->right==now){
                    vwall[prev->y][prev->x]=false;
                }
                else vwall[now->y][now->x]=false;
            }
            board[now->y][now->x]->visited=true;
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                cout<<board[i][j]->visited;
            }
            cout<<endl;
        }
        if(cnt<row*col){
            back=rand()%10;
            vector<Point*> temp;
            if(back<5){
                A:;
                if(now->up!=NULL)temp.push_back(now->up);
                if(now->right!=NULL)temp.push_back(now->right);
                if(now->down!=NULL)temp.push_back(now->down);
                if(now->left!=NULL)temp.push_back(now->left);
                dfs(temp[rand()%temp.size()],now,cnt);
            }
            else{
                if(now->up!=NULL&&now->up->visited!=true)temp.push_back(now->up);
                if(now->right!=NULL&&now->right->visited!=true)temp.push_back(now->right);
                if(now->down!=NULL&&now->down->visited!=true)temp.push_back(now->down);
                if(now->left!=NULL&&now->left->visited!=true)temp.push_back(now->left);
                if(temp.size()==0)goto A;
                dfs(temp[rand()%temp.size()],now,cnt);
            }
        }
    }

完整构造函数：

Maze(int n,int m):row(n),col(m){
        int i,j;
        vector<Point*> tempv;
        for(i=0;i<row;i++)vwall.push_back(vector<bool>(col-1,true));
        for(i=0;i<col;i++)hwall.push_back(vector<bool>(row-1,true));
        for(i=0;i<row;i++){
            for(j=0;j<col;j++){
                Point *temppt=new Point(j,i);
                tempv.push_back(temppt);
            }
            board.push_back(tempv);
        }
        for(i=0;i<row;i++){
            for(j=0;j<col;j++){
                if(i!=0)board[i][j]->up=board[i-1][j];
                if(i!=row-1)board[i][j]->down=board[i+1][j];
                if(j!=0)board[i][j]->left=board[i][j-1];
                if(j!=col-1)board[i][j]->right=board[i][j+1];
            }
        }
        dfs(board[0][0],NULL,0);
    }

Answer 1

将 tempv 推回板后，您并没有清除它。所以 board 的每个条目都接收到 tempv 的扩展副本。（具体来说，每行中的前 col 个条目将相同。）

只需在 board.push_back(tempv) 之后调用 tempv.clear()，这样每一行都以一个空向量开始。

以结构格式操作数据最终变得很奇怪

Manipulating data in struct format ends up weird

c++

depth-first-search