关于广搜
  • 板块学术版
  • 楼主PvbeLLN
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/10/23 23:55
  • 上次更新2024/10/24 11:43:26
查看原帖
关于广搜
820947
PvbeLLN楼主2024/10/23 23:55

这是我某道广搜题代码的一部分。

A

void bfs(int x,int y,int who) {
    queue<node> q;
    q.push({x,y,0});
    while (q.size()) {
        node now=q.front();
        q.pop();
        nowx=now.x;
        nowy=now.y;
        nowstep=now.step;
        if (vis[nowx][nowy]) continue;  //<--
        vis[nowx][nowy]=1;
        if (who==1) time1[nowx][nowy]=nowstep;
        else time2[nowx][nowy]=nowstep;
        for (int i=0;i<4;i++) {
            nx=nowx+dirx[i];
            ny=nowy+diry[i];
            if (nx<1||nx>n||ny<1||ny>m||a[nx][ny]=='#') continue;
            
            q.push({nx,ny,nowstep+1});
        }
    }
}

B

void bfs(int x,int y,int who) {
    queue<node> q;
    q.push({x,y,0});
    while (q.size()) {
        node now=q.front();
        q.pop();
        nowx=now.x;
        nowy=now.y;
        nowstep=now.step;
        
        vis[nowx][nowy]=1;
        if (who==1) time1[nowx][nowy]=nowstep;
        else time2[nowx][nowy]=nowstep;
        for (int i=0;i<4;i++) {
            nx=nowx+dirx[i];
            ny=nowy+diry[i];
            if (nx<1||nx>n||ny<1||ny>m||a[nx][ny]=='#') continue;
            if (vis[nx][ny]) continue; //<--
            q.push({nx,ny,nowstep+1});
        }
    }
}

vis 判定的位置不对,为何结果就不对?

(A 版本 AC,B 版本 TLE)

2024/10/23 23:55
加载中...