深入理解BFS

发表于

如果把问题的状态空间看作一张图，广度优先搜索便是对这张图进行广度优先遍历

在整个过程中，不断从队头取出状态，对于该状态面临的所有分支，把沿着每条分支到达的下一状态（尚未访问过或者能够被更新为更优解）插入队尾，直到队尾为空。

广搜是逐层遍利搜索数的算法所有状态按照入队的先后顺序具有层次调调性。

如果每一次拓展恰好对应一步，那么当一个状态第一次被访问（入队时），就得到了从初始状态到该状态的最小步数

因此，广搜很利于解决类似于走地图的的flood-fill问题，即从起点到达某个位置的最短步数

例题

给定一个N行M列的01矩阵A，A[i][j]与A[k][l]之间的曼哈顿距离定义为

dist(A[i][j],A[k][l])=|i-k|+|j-l|

输出一个N行M列的整数矩阵B，其中

B[i][j]=min{dist(A[i][j],A[x][y])}(x∈[1,N],y∈[1,M],A[x][y]=1)

N,M<=1000

这好像是一个flood-fill问题

但是我们也发现，这个问题有多个起始状态，因为没有明确的起点。

我们把A中的每一个1都看作起点，整个矩阵的所有位置都可通行

在这种具有多个等价的起始状态的问题中，我们在BFS之前把这些起始状态插入队列中，逐层搜索，依次拓展，首解最优

当每个位置(x,y)第一次访问时,就相当于距离它最近的那个起点拓展到了(x,y)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <queue>
#include <iostream>
using namespace std;
int n,m;
char s[1010][1010];
int d[1010][1010];
queue<pair<int,int>>q;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    scanf("%s",s[i]+1);
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    d[i][j]=-1;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    if(s[i][j]=='1')q.push(make_pair(i,j)),d[i][j]=0;
    while(q.size()){
        pair<int,int>now=q.front();
        q.pop();
        for(int i=0;i<4;++i){
            pair<int,int>next(now.first+dx[i],now.second+dy[i]);
            if(next.first<1||next.second<1||next.first>n||next.second>m)continue;
            if(d[next.first][next.second]==-1){
                d[next.first][next.second]=d[now.first][now.second]+1;
                q.push(next);
            }
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)printf("%d ",d[i][j]);
        puts("");
    }
}