01 BFS/双端队列 BFS

· · 算法·理论

OIWiki

Part 1 什么是 01 BFS

边权值为可能有，也可能没有（由于 BFS 适用于权值为 1 的图，所以一般权值是 0 或 1），或者能够转化为这种边权值的最短路问题。

例如在走迷宫问题中，你可以花 1 个金币走 5 步，也可以不花金币走 1 步，这就可以用 0-1 BFS 解决。

01 BFS，又称双端队列 BFS，是一种仅适用于边权为 0/1 的情况（也即，存在或不存在）。

01 BFS 一般使用双端队列 deque 解决。

Part 2 01 BFS 的原理

考虑双端队列实现。

01 BFS 使用“0先1后”的优化方法来保证队列内有序。

也即：

01 BFS 具备着“第一次到某个点所需要的代价就是这个点的最小代价”的性质。

有序性的证明

证明：

初始时队列仅有一个元素 0，队列有序。

对于每一次操作：

我们记每一次操作时的队首为 x，取出后队列有序，且仅含 x,x+1。（可以试着去证明，这里默认都知道。）

显然，此时队列里仅含 x,x+1 这两种元素，队列有序。

Part 3 01 BFS 的实现

稍微改了一下 OIWiki 上的伪代码：

while (队列不为空) {
  int u = 队首;
  弹出队首;
  if (u 满足最终状态) {
    结束;
  }
  for (枚举 u 的邻居) {
    更新数据
    if (...)
      添加到队首;
    else
      添加到队尾;
  }
}
搜索失败;

实际上写起来和普通的 BFS 大同小异，只不过要注意把 queue 的语法改成 deque 的语法。

Part 4 01 BFS 的例题

SP22393

题目简述：

  • 现在你在一个 n\times m 的棋盘上，你在 (1,1)，要去 (n,m)。
  • 你每次可以移动到你四周的方格。如果你目前所在的方格对应的字母与你要去的方格的字母不同，那么这次移动产生 1 的代价，否则不产生。
  • 求出去往 (n,m) 的最小代价。

典型的 01 BFS。

考虑每次向四周，按照题目要求的求出代价。

回顾上文提到过的特征，第一次到终点的代价就是最小代价。

到此，你就可以尝试自己完成了。下面给出 AC 代码：

#include<bits/stdc++.h>
using namespace std;
struct point
{
    int x,y;
};
deque<point> dq,emp;
int n,m,p[1005][1005],dis[1005][1005],t;
void bfs()
{
    while(!dq.empty())
    {
        point f=dq.front();
        dq.pop_front();
        if(f.x==n&&f.y==m)
        {
            cout<<dis[n][m]<<endl;
            return;
        }
        point now;
        now={f.x+1,f.y};
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]==p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+0)
        {
            dq.push_front(now);
            dis[now.x][now.y]=dis[f.x][f.y];
        }
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]!=p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+1)
        {
            dq.push_back(now);
            dis[now.x][now.y]=dis[f.x][f.y]+1;
        }
        now={f.x-1,f.y};
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]==p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+0)
        {
            dq.push_front(now);
            dis[now.x][now.y]=dis[f.x][f.y];
        }
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]!=p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+1)
        {
            dq.push_back(now);
            dis[now.x][now.y]=dis[f.x][f.y]+1;
        }
        now={f.x,f.y+1};
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]==p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+0)
        {
            dq.push_front(now);
            dis[now.x][now.y]=dis[f.x][f.y];
        }
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]!=p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+1)
        {
            dq.push_back(now);
            dis[now.x][now.y]=dis[f.x][f.y]+1;
        }
        now={f.x,f.y-1};
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]==p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+0)
        {
            dq.push_front(now);
            dis[now.x][now.y]=dis[f.x][f.y];
        }
        if(now.x>=1&&now.x<=n&&now.y>=1&&now.y<=m&&p[f.x][f.y]!=p[now.x][now.y]&&dis[now.x][now.y]>dis[f.x][f.y]+1)
        {
            dq.push_back(now);
            dis[now.x][now.y]=dis[f.x][f.y]+1;
        }
    }
    cout<<-1<<endl;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        char ch;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= m; j++)
            {
                cin>>ch;
                p[i][j]=ch;
            }
        }
        memset(dis,0x3f,sizeof(dis));
        dis[1][1]=0;
        dq=emp;
        dq.push_back({1,1});
        bfs();
    }
}