原题单链接：https://www.luogu.com.cn/paste/sa0zary9 || https://rentry.org/3r68rga7

广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索", BFS是用于图的查找算法(要求能用图表示出问题的关联性)。

BFS可用于解决2类问题：

1.从A出发是否存在到达B的路径；DFS也可求

2.从A出发到达B的最短路径；数据小20以内的话, DFS也不是不可以题眼

整体思路

其思路为从图上一个节点出发，访问先访问其直接相连的子节点，若子节点不符合，再问其子节点的子节点，按级别顺序(一层一层)依次访问，直到访问到目标节点。

步骤

起始：将起点（源点，树的根节点）放入队列中
扩散：从队列中取出队头的结点，将它的相邻结点放入队列，不断重复这一步
终止：当队列为空时，说明我们遍历了所有的能到的结点，整个图能到的点都被搜索了一遍

时空复杂度

时间复杂度 : 最差情形下，BFS必须寻找所有到可能节点的所有路径，因此其时间复杂度为O(|V| + |E|)，其中|V|是节点的数目，而|E|是图中边的数目。

空间复杂度 : BFS的空间复杂度为 O(B^h)，其中B是最大分支系数，而h是树的最长路径长度(树的高度) 。由于对空间的大量需求，因此BFS并不适合解非常大的问题。

对于所有边长度相同的情况，比如地图的模型，bfs第一次遇到目标点，此时就一定是从根节点到目标节点最短的路径（因为每一次所有点都是向外扩张一步，你先遇到，那你就一定最短）。bfs先找到的一定是最短的。但是如果是加权边的话这样就会出问题了，bfs传回的是经过边数最少的解，但是因为加权了，这个解到根节点的距离不一定最短。比如1000+1000是只有两段，1+1+1+1有4段，由于bfs返回的经过边数最少的解，这里会返回总长度2000的那个解，显然不是距离最短的路径。此时我们就应该采用Dijkstra最短路算法解决加权路径的最短路了。

SPFA

例题

AcWing 844 走迷宫

输入 n×m 的 0/1 网格，0 可通行；起点、终点均须可通行。入队时标记距离，避免重复访问。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m; cin >> n >> m;
    vector<vector<int>> g(n,vector<int>(m)),d(n,vector<int>(m,-1));
    for(auto &row:g) for(auto &x:row) cin >> x;
    queue<pair<int,int>> q; q.push({0,0}); d[0][0]=0;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    while(!q.empty()) {
        auto [x,y]=q.front(); q.pop();
        for(int i=0;i<4;++i) { int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>=n || b<0 || b>=m || g[a][b] || d[a][b]!=-1) continue;
            d[a][b]=d[x][y]+1; q.push({a,b}); }
    }
    cout << d[n-1][m-1] << '\n';
}

P1746 离开中山路

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<string> g(n); for(auto &s:g) cin >> s;
    int sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty; --sx; --sy; --tx; --ty;
    vector<vector<int>> d(n,vector<int>(n,-1)); queue<pair<int,int>> q; q.push({sx,sy}); d[sx][sy]=0;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    while(!q.empty()) { auto [x,y]=q.front(); q.pop();
        for(int i=0;i<4;++i) { int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>=n || b<0 || b>=n || g[a][b]!='0' || d[a][b]!=-1) continue;
            d[a][b]=d[x][y]+1; q.push({a,b}); }
    }
    cout << d[tx][ty] << '\n';
}

马的遍历

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m,x,y; cin >> n >> m >> x >> y; --x; --y;
    vector<vector<int>> d(n,vector<int>(m,-1)); queue<pair<int,int>> q; q.push({x,y}); d[x][y]=0;
    int dx[]={-2,-1,1,2,2,1,-1,-2},dy[]={1,2,2,1,-1,-2,-2,-1};
    while(!q.empty()) { auto [x,y]=q.front(); q.pop(); for(int i=0;i<8;++i) {
        int a=x+dx[i],b=y+dy[i]; if(a<0 || a>=n || b<0 || b>=m || d[a][b]!=-1) continue;
        d[a][b]=d[x][y]+1; q.push({a,b}); } }
    for(auto &row:d) { for(int v:row) cout << left << setw(5) << v; cout << '\n'; }
}

多源 BFS：最近源点距离

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m,a,b; cin >> n >> m >> a >> b;
    vector<vector<int>> d(n+1,vector<int>(m+1,-1)); queue<pair<int,int>> q;
    while(a--) { int x,y; cin >> x >> y; if(d[x][y]==-1) { d[x][y]=0; q.push({x,y}); } }
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    while(!q.empty()) { auto [x,y]=q.front(); q.pop(); for(int i=0;i<4;++i) {
        int u=x+dx[i],v=y+dy[i]; if(u<1 || u>n || v<1 || v>m || d[u][v]!=-1) continue;
        d[u][v]=d[x][y]+1; q.push({u,v}); } }
    while(b--) { int x,y; cin >> x >> y; cout << d[x][y] << '\n'; }
}

填涂颜色：从棋盘外部洪泛

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<vector<int>> g(n+2,vector<int>(n+2)),seen=g;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cin >> g[i][j];
    queue<pair<int,int>> q; q.push({0,0}); seen[0][0]=1;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    while(!q.empty()) { auto [x,y]=q.front(); q.pop(); for(int i=0;i<4;++i) {
        int a=x+dx[i],b=y+dy[i]; if(a<0 || a>n+1 || b<0 || b>n+1 || g[a][b] || seen[a][b]) continue;
        seen[a][b]=1; q.push({a,b}); } }
    for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) cout << (g[i][j]?1:seen[i][j]?0:2) << ' '; cout << '\n'; }
}

流星雨

坐标范围按原题 0～300 设置，额外保留一圈安全区域。

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int N=305,INF=1000000000;
    vector<vector<int>> fire(N,vector<int>(N,INF)),d(N,vector<int>(N,-1));
    int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0}; int m; cin >> m;
    while(m--) { int x,y,t; cin >> x >> y >> t; for(int i=0;i<5;++i) {
        int a=x+dx[i],b=y+dy[i]; if(a>=0 && a<N && b>=0 && b<N) fire[a][b]=min(fire[a][b],t); } }
    if(fire[0][0]==0) { cout << -1 << '\n'; return 0; }
    queue<pair<int,int>> q; q.push({0,0}); d[0][0]=0;
    while(!q.empty()) { auto [x,y]=q.front(); q.pop(); if(fire[x][y]==INF) { cout << d[x][y] << '\n'; return 0; }
        for(int i=0;i<4;++i) { int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>=N || b<0 || b>=N || d[a][b]!=-1 || d[x][y]+1>=fire[a][b]) continue;
            d[a][b]=d[x][y]+1; q.push({a,b}); } }
    cout << -1 << '\n';
}

越野滑雪：二分允许的最大高度差

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m,n; cin >> m >> n; vector<vector<int>> h(m,vector<int>(n)),flag=h;
    for(auto &row:h) for(auto &x:row) cin >> x;
    int sx=0,sy=0,total=0,lo=INT_MAX,hi=INT_MIN;
    for(int i=0;i<m;++i) for(int j=0;j<n;++j) { cin >> flag[i][j]; if(flag[i][j]) { sx=i; sy=j; ++total; } lo=min(lo,h[i][j]); hi=max(hi,h[i][j]); }
    auto check=[&](int limit) {
        vector<vector<bool>> seen(m,vector<bool>(n)); queue<pair<int,int>> q; q.push({sx,sy}); seen[sx][sy]=true; int cnt=0;
        int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
        while(!q.empty()) { auto [x,y]=q.front(); q.pop(); cnt+=flag[x][y];
            for(int i=0;i<4;++i) { int a=x+dx[i],b=y+dy[i];
                if(a<0 || a>=m || b<0 || b>=n || seen[a][b] || abs(h[a][b]-h[x][y])>limit) continue;
                seen[a][b]=true; q.push({a,b}); } }
        return cnt==total;
    };
    int l=0,r=hi-lo; while(l<r) { int mid=(l+r)/2; if(check(mid)) r=mid; else l=mid+1; } cout << l << '\n';
}

魔板：状态搜索与路径还原

状态按棋盘外圈顺时针编码；按 A、B、C 顺序扩展以确定最短操作序列。

#include <bits/stdc++.h>
using namespace std;

string moveState(string s,int op) {
    string t=s;
    if(op==0) reverse(t.begin(),t.end());
    if(op==1) { int p[]={3,0,1,2,5,6,7,4}; for(int i=0;i<8;++i) t[i]=s[p[i]]; }
    if(op==2) { t[1]=s[6]; t[2]=s[1]; t[5]=s[2]; t[6]=s[5]; }
    return t;
}
int main() {
    string start="12345678",target; for(int i=0,x;i<8;++i) { cin >> x; target+=char('0'+x); }
    queue<string> q; unordered_map<string,pair<string,char>> pre; q.push(start); pre[start]={"",0};
    while(!q.empty()) { string s=q.front(); q.pop(); if(s==target) break;
        for(int i=0;i<3;++i) { string t=moveState(s,i); if(pre.count(t)) continue; pre[t]={s,char('A'+i)}; q.push(t); } }
    string ans; for(string t=target;t!=start;t=pre[t].first) ans+=pre[t].second;
    reverse(ans.begin(),ans.end()); cout << ans.size() << '\n' << ans << '\n';
}

0-1 BFS：相同字符边权为 0

坐标从 0 开始。必须按更短距离松弛，不能将首次入队视为最短距离已经确定。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,m;
    while(cin >> n >> m && n && m) {
        vector<string> g(n); for(auto &s:g) cin >> s; int sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty;
        vector<vector<int>> d(n,vector<int>(m,INT_MAX)); deque<pair<int,int>> q; q.push_front({sx,sy}); d[sx][sy]=0;
        int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
        while(!q.empty()) { auto [x,y]=q.front(); q.pop_front(); for(int i=0;i<4;++i) {
            int a=x+dx[i],b=y+dy[i]; if(a<0 || a>=n || b<0 || b>=m) continue;
            int w=(g[x][y]!=g[a][b]); if(d[x][y]+w>=d[a][b]) continue;
            d[a][b]=d[x][y]+w; if(w) q.push_back({a,b}); else q.push_front({a,b}); } }
        cout << d[tx][ty] << '\n';
    }
}

双向搜索：网格的两端同时扩展

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n; vector<string> g(n); for(auto &s:g) cin >> s;
    int sx,sy,tx,ty; cin >> sx >> sy >> tx >> ty; --sx; --sy; --tx; --ty;
    if(sx==tx && sy==ty) { cout << 0 << '\n'; return 0; }
    vector<vector<int>> d(n,vector<int>(n,-1)),side(n,vector<int>(n)); queue<pair<int,int>> q;
    q.push({sx,sy}); q.push({tx,ty}); d[sx][sy]=d[tx][ty]=0; side[sx][sy]=1; side[tx][ty]=2;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    while(!q.empty()) { auto [x,y]=q.front(); q.pop(); for(int i=0;i<4;++i) {
        int a=x+dx[i],b=y+dy[i]; if(a<0 || a>=n || b<0 || b>=n || g[a][b]!='0') continue;
        if(side[a][b] && side[a][b]!=side[x][y]) { cout << d[x][y]+d[a][b]+1 << '\n'; return 0; }
        if(side[a][b]) continue; side[a][b]=side[x][y]; d[a][b]=d[x][y]+1; q.push({a,b}); } }
    cout << -1 << '\n';
}

八数码：单向 BFS

#include <bits/stdc++.h>
using namespace std;

vector<string> nextStates(string s) {
    vector<string> out; int p=s.find('0'),x=p/3,y=p%3;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    for(int i=0;i<4;++i) { int a=x+dx[i],b=y+dy[i]; if(a<0 || a>=3 || b<0 || b>=3) continue;
        swap(s[p],s[a*3+b]); out.push_back(s); swap(s[p],s[a*3+b]); }
    return out;
}
int main() {
    string start,target="123804765"; cin >> start; queue<string> q; unordered_map<string,int> d; q.push(start); d[start]=0;
    while(!q.empty()) { string s=q.front(); q.pop(); if(s==target) { cout << d[s] << '\n'; return 0; }
        for(auto t:nextStates(s)) if(!d.count(t)) { d[t]=d[s]+1; q.push(t); } }
    cout << -1 << '\n';
}

八数码：双向 BFS

#include <bits/stdc++.h>
using namespace std;

vector<string> nextStates(string s) {
    vector<string> out; int p=s.find('0'),x=p/3,y=p%3;
    int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
    for(int i=0;i<4;++i) { int a=x+dx[i],b=y+dy[i]; if(a<0 || a>=3 || b<0 || b>=3) continue;
        swap(s[p],s[a*3+b]); out.push_back(s); swap(s[p],s[a*3+b]); }
    return out;
}
int main() {
    string start,target="123804765"; cin >> start;
    if(start==target) { cout << 0 << '\n'; return 0; }
    queue<string> q; unordered_map<string,int> d,side; q.push(start); q.push(target); d[start]=d[target]=0; side[start]=1; side[target]=2;
    while(!q.empty()) { string s=q.front(); q.pop(); for(auto t:nextStates(s)) {
        if(side.count(t)) { if(side[t]!=side[s]) { cout << d[s]+d[t]+1 << '\n'; return 0; } continue; }
        side[t]=side[s]; d[t]=d[s]+1; q.push(t); } }
    cout << -1 << '\n';
}

作业 (上节课DFS过不去, 这节课可以用BFS试一试~)

P1135 奇怪的电梯 dfs暴力过不去

Flood fill — 找连通块

P1596 Lake Counting S

P1451求细胞数量

P1331 海战

P1767 家族

SP15436 UCV2013H - Slick

迷宫问题

P1683 入门

P1605 迷宫

P1443 马的遍历

P1747 好奇怪的游戏

P2298 Mzc和男家丁的游戏

关于memset和0x3f

int a[100];

memset(a,0x3f,sizeof(a) );

0x3f=0011 1111=63

C++中int型变量所占的位数为4个字节，即32位

0x3f显然不是int型变量中单个字节的最大值，应该是0x7f=0111 1111 B

那为什么要赋值0x3f ??

int

1.作为无穷大使用

因为4个字节均为0x3f时，0x3f3f3f3f的十进制是1061109567，也就是10^ 9级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。

2.可以保证无穷大加无穷大仍然不会超限。

另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了**“无穷大加一个有穷的数依然是无穷大”），事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int_MAX的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求**。

首先要知道memset函数是以字节为单位进行赋值的；

void memset(void *s, int ch, size_t n);

函数解释：将s中前n个字节（typedef unsigned int size_t ）用 ch 替换并返回 s 。

其实这里面的ch就是ascii为ch的字符；

将s所指向的某一块内存中的前n个字节的内容全部设置为ch指定的ASCII值