01BFS

cqbzlzm · 2023-08-07 23:00:26 · 算法·理论

01BFS

如果图的边权全部都为1，那么用普通的BFS就可以解决。但如果边权不等，就需要一个优先队列，时间复杂度带了一个log。对于边权为0 或 1 的图，就产生了一个O(v+e)(点数+边数)的算法，称为01BFS。

01BFS利用一个双端队列(deque)来维护搜索扩展出来的结点。当边权为0时，使用push_front把新结点压入队列头部。当边权为1时，使用push_back把新结点压入队列尾部。这样可以保证队列里面元素的单调性，保证最先出队的节点代价一定小于等于后出队的节点代价，保证某个点第一次遍历时的答案一定是最佳的答案。

对于算法正确性，由于01BFS队列内的所有节点当前答案一定只有两个，分为前面一部分和后面一部分，每次取出都是从队首取出，队首元素和遍历到的元素之间的代价如果为1，则当前代价加1后一定是最大的（或并列最大），而如果代价为0，则答案不变，因为取出的是队首的（最小的）所以遍历到的还是最小的，满足条件。

Ocean Currents

题意： 在一个n\times m的海面上，每个格子的水往各自的方向流，共8个方向，在一个格子上，顺水不用带代价，与水方向不同则要1的代价，求从一个位置到另一个位置的最小代价

分析：往一个方向走，要么代价为1，要么代价为0，所以这是一个01BFS。需要注意的是，不一定先遍历到的点的权值最小，但可以保证先出队的是最小的，所以我们不能用一个bool的vis来判断走过没，而要用一个int的dis存距离，通过dis的大小来判断是否入队

bool check(int x,int y){
    return x<=n&&x>=1&&y<=m&&y>=1;
}
void bfs(int bx,int by,int ex,int ey){
    memset(dist,-1,sizeof(dist));
    deque<node>q;
    q.push_front({bx,by,0});
    while(!q.empty()){
        int x=q.front().x;
        int y=q.front().y;
        int val=q.front().val;
        q.pop_front();
        if(dist[x][y]!=-1){
            continue;
        }
        dist[x][y]=val;
        if(x==ex&&y==ey){
            printf("%d")
            printf("%d\n",dist[x][y]);
            return ;
        }

        for(int i=0;i<8;i++){
            int nx=x+dirx[i];
            int ny=y+diry[i];
            if(check(nx,ny)==0){
                continue;
            }
            if(int(a[x][y]-'0')==i){
                q.push_front({nx,ny,val});
            } else{
                q.push_back({nx,ny,val+1});
            }
        }
    }
    return;
}

Labyrinth

题意： 一个n\times m的迷宫，每一步可以向上下左右移动一格，但向左移动不超过l格，并且向右移动不超过r格。向上和向下的移动次数没有限制。求一共能到达多少个格子

分析： 假设迷宫起始起点为(x0,y0) ， 我们要看能否到达(x1,y1)，假设过程中向左走了L格，向右走了R格，则有y1-y0=R-L。我们只需要再求出左右一共最少走了多少格，就可以算出L和R。这一步用01BFS，将上下走的代价设为0，左右走为1

void bfs(int bx,int by){
    memset(dist,0x3f3f3f3f,sizeof(dist));
    deque<node>q;
    q.push_front({bx,by});
    dist[bx][by]=0;
    while(!q.empty()){
        int x=q.front().x;
        int y=q.front().y;
        q.pop_front();
        for(int i=0;i<4;i++){
            int nx=x+dirx[i];
            int ny=y+diry[i];
            if(check(nx,ny)==0){
                continue;
            }
            int w=(diry[i]!=0);
            if(dist[nx][ny]>dist[x][y]+w){
                dist[nx][ny]=dist[x][y]+w;
                if(!w){
                    q.push_front({nx,ny});
                } else{
                    q.push_back({nx,ny});
                }
            }
        }
    }
    return;
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(dist[i][j]==0x3f3f3f3f){
            continue;
        }
        int a=j-by;//r-l=a; r+l=dist
        int l=(dist[i][j]-a)/2;
        int r=(a+dist[i][j])/2;
        if(l<=L&&r<=R){
            ans++;
        }
    }
}