原题单链接：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
例题
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 110;
typedef pair<int,int> pii;
int n,m;
int g[N][N];
int dist[N][N];
queue<pii> q;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int bfs(int sx,int sy)
{
memset(dist,-1,sizeof dist); // -1 means not visited
q.push({sx,sy});
dist[sx][sy]=0; // start point
while (q.size()&&!q.empty()) // while queue is not empty
{
auto t=q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int a=t.x+dx[i],b=t.y+dy[i];
if(a<1||a>n||b<1||b>m) continue; // out of bound
if(g[a][b]!=0) continue; // if there is a wall
if(dist[a][b]>0) continue; // if already visited
q.push({a,b}); // push the next point
dist[a][b]=dist[t.x][t.y]+1;
if(a==n&&b==m)
{
return dist[a][b];
}
}
}
return dist[n][m];
}
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin >> g[i][j];
}
}
int res=bfs(1,1);
cout << res;
}若打不开这个题就看这个 P1746 离开中山路
代码见下文。习题课
热身 – 简单迷宫问题
P1746 离开中山路 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1010;
int n;
int mx1,my1,mx2,my2;
char g[N][N];
int dist[N][N];
int res;
queue<pii> q;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int bfs(int x,int y)
{
memset(dist,-1,sizeof(dist));
q.push({x,y});
dist[x][y]=0;
while (!q.empty())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<1||a>n||b<1||b>n)continue;
if(g[a][b]!='0')continue;
if(dist[a][b]>=0)continue;
q.push({a,b});
dist[a][b]=dist[t.first][t.second]+1;
if(a==mx2&&b==my2)
{
return dist[a][b];
}
}
}
return dist[mx2][my2];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
}
}
// for(int i=1;i<=n;i++)
// {
// cin>>g[i]+1;
// }
cin>>mx1>>my1;
cin>>mx2>>my2;
res=bfs(mx1,my1);
cout<<res<<'\n';
return 0;
}P1443 马的遍历 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=410;
int n,m,x,y;
int dist[N][N];
pii q[N*N];
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2,-1};
void bfs(int x,int y)
{
memset(dist,-1,sizeof(dist));
q[0]={x,y};
dist[x][y]=0;
int hh=0,tt=0;
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<8;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<1||a>n||b<1||b>m)continue;
if(dist[a][b]>=0)continue;
dist[a][b]=dist[t.first][t.second]+1;
q[++tt]={a,b};
}
}
}
int main()
{
scanf("%d %d %d %d",&n,&m,&x,&y);
bfs(x,y);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
printf("%-5d",dist[i][j]);
}
printf("\n");
}
}————–P1747 好奇怪的游戏 (跑2次) 0
————–P2385 Bronze Lilypad Pond B 可控马步
多源BFS
P1332 血色先锋队 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=510;
int n,m,a,b;
int dist[N][N];
pii q[N*N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int hh=0,tt=-1;
void bfs()
{
while(hh<=tt){
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<1||a>n||b<1||b>m)continue;
if(dist[a][b]>=0)continue;
dist[a][b]=dist[t.first][t.second]+1;
q[++tt]={a,b};
}
}
}
int main()
{
cin>>n>>m>>a>>b;
memset(dist,-1,sizeof(dist));
while(a--)
{
int x,y;
cin>>x>>y;
q[++tt]={x,y};
dist[x][y]=0;
}
bfs();
while(b--)
{
int x,y;
cin>>x>>y;
cout<<dist[x][y]<<'\n';
}
return 0;
}——————–acw173.矩阵距离 0
染色问题
P1162 填涂颜色9 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=40;
int n;
int g[N][N];
bool st[N][N];
pii q[N*N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void bfs(int x,int y)
{
q[0]={x,y};
st[x][y]=true;
int hh=0,tt=0;
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<0||a>n+1||b<0||b>n+1)continue;
if(st[a][b])continue;
if(g[a][b]==1)continue;
st[a][b]=true;
q[++tt]={a,b};
}
}
return;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>g[i][j];
}
}
bfs(0,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(g[i][j]==0&&!st[i][j])g[i][j]=2;
cout<<g[i][j]<<' ';
}
cout<<'\n';
}
return 0;
}———————–P1506 拯救oibh总部
———————–CF1059B Forgery
有外界干扰的迷宫问题
P2895 Meteor Shower S 天降陨石 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=310;
int m;
int dist[N][N];
int fire[N][N];
pii q[N*N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int bfs()
{
q[0]={0,0};
dist[0][0]=0;
int hh=0,tt=0;
while(hh<=tt)
{
auto t=q[hh++];
for(int i=0;i<4;i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<0||b<0)continue; // 超出边界
if(dist[a][b]>=0)continue; // 已访问过
if(dist[t.first][t.second]+1>=fire[a][b])continue; // 预先检查，如果被砸死了就不用管这个点了
dist[a][b]=dist[t.first][t.second]+1;
q[++tt]={a,b};
if(fire[a][b]==0x3f3f3f3f)return dist[a][b];
}
}
return -1;
}
int main()
{
cin>>m;
memset(fire,0x3f,sizeof(fire));
memset(dist,-1,sizeof(dist));
while (m--)
{
int x,y,t;
cin>>x>>y>>t;
fire[x][y]=min(t,fire[x][y]);
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0||a>301||b<0||b>301)continue;
fire[a][b]=min(t,fire[a][b]);
}
}
int res=bfs();
cout<<res<<'\n';
return 0;
}——————–P3395 路障 天降路障 0.5
看起来比较困难的BFS
P2658 汽车拉力比赛 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 510;
int m, n;
int high[N][N];
int flag[N][N];
int cnt_flag = 0;
pii q[N * N];
int x = 0, y = 0;
bool st[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool check(int mid)
{
q[0] = {x, y};
st[x][y]=true;
int cnt = 1;
int hh = 0, tt = 0;
while (hh <= tt)
{
auto t = q[hh++];
for (int i = 0; i < 4; i++)
{
int a = t.first + dx[i], b = t.second + dy[i];
if (a < 1 || a > m || b < 1 || b > n)
continue;
if (st[a][b])
continue;
if (abs(high[t.first][t.second] - high[a][b]) > mid)
continue;
q[++tt] = {a, b};
st[a][b] = true;
if (flag[a][b] == 1)
{
cnt++;
if (cnt == cnt_flag)
{
return true;
}
}
}
}
return false;
}
int main()
{
cin >> m >> n;
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> high[i][j];
}
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> flag[i][j];
if (flag[i][j] == 1)
{
cnt_flag++;
}
}
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (flag[i][j] == 1)
{
x = i, y = j;
i = m + 1;
break;
}
}
}
int l = -1, r = 1e9 + 10;
while (l + 1 < r)
{
int mid = (l + r) / 2;
memset(q, 0, sizeof(q));
memset(st, false, sizeof(st));
if (check(mid))
{
r = mid;
}
else
l = mid;
}
cout << r;
return 0;
}————–P1126 机器人搬重物
P2730 魔板 Magic Squares
#include <bits/stdc++.h>
using namespace std;
int g[2][4];
unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> pre;
queue<string> q;
void set1(string state)
{
for (int i = 0; i < 4; i++)
{
g[0][i] = state[i];
}
for (int i = 3, j = 4; i >= 0; i--, j++)
{
g[1][i] = state[j];
}
}
string get1()
{
string res;
for (int i = 0; i < 4; i++)
{
res += g[0][i];
}
for (int i = 3; i >= 0; i--)
{
res += g[1][i];
}
return res;
}
// 交换上下两行，A
string move0(string state)
{
set1(state);
for (int i = 0; i < 4; i++)
{
swap(g[0][i], g[1][i]);
}
return get1();
}
// 将最右边的一列移动到最左边，B
string move1(string state)
{
set1(state);
char v0 = g[0][3], v1 = g[1][3];
for (int i = 3; i > 0; i--)
{
g[0][i] = g[0][i - 1];
g[1][i] = g[1][i - 1];
}
g[0][0] = v0, g[1][0] = v1;
return get1();
}
// 中央四个元素顺时针旋转，C
string move2(string state)
{
set1(state);
char v0 = g[0][1], v1 = g[0][2], v2 = g[1][2], v3 = g[1][1];
g[0][1] = v3, g[0][2] = v0, g[1][2] = v1, g[1][1] = v2;
return get1();
}
int bfs(string start, string end)
{
q.push(start);
dist[start] = 0;
while (q.size())
{
auto t = q.front();
q.pop();
if (t == end)
{
return dist[t];
}
string m[3];
m[0] = move0(t), m[1] = move1(t), m[2] = move2(t);
for (int i = 0; i < 3; i++)
{
if (!dist.count(m[i]))
{
dist[m[i]] = dist[t] + 1;
pre[m[i]] = {'A' + i, t};
q.push(m[i]);
}
}
}
return -1;
}
int main()
{
int x;
string start = "12345678", end;
while (cin >> x)
{
end += char(x + '0');
}
int res = bfs(start, end);
cout << res << endl;
string path;
while (end != start)
{
path += pre[end].first;
end = pre[end].second;
}
reverse(path.begin(), path.end());
if (path.size())
cout << path << endl;
return 0;
}双端队列广搜
P4554 小明的游戏 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 510;
int n,m,xx1,yy1,xx2,yy2;
char g[N][N];
int dist[N][N];
deque<pii> q;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int bfs(int x,int y)
{
q.push_back({x,y});
dist[x][y]=0;
while (q.size())
{
auto t=q.front();
q.pop_front();
char ch=g[t.first][t.second];
for (int i = 0; i < 4; i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<0||a>=n||b<0||b>=m)continue;
if(dist[a][b]>=0)continue;
if(g[a][b]==ch)
{
dist[a][b]=dist[t.first][t.second];
q.push_front({a,b});
}
if(g[a][b]!=ch)
{
dist[a][b]=dist[t.first][t.second]+1;
q.push_back({a,b});
}
if(a==xx2&&b==yy2)return dist[xx2][yy2];
}
}
return -1;
}
int main()
{
while (cin >> n >> m, n != 0 && m != 0)
{
for (int i = 0; i < n; i++)
{
cin >> g[i];
}
memset(dist,-1,sizeof(dist));
q.clear();
cin>>xx1>>yy1>>xx2>>yy2;
int res =bfs(xx1,yy1);
cout<<res<<'\n';
}
return 0;
}————————–P3596 棋盘
————————–P4667 Switch the Lamp On
双向广搜
P1746 离开中山路 1
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=1100;
int n;
char g[N][N];
int dist[N][N];
int vis[N][N];
pii q[N*N];
int xx1,yy1,xx2,yy2;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int bfs()
{
memset(dist,-1,sizeof(dist));
memset(vis,-1,sizeof(vis));
dist[xx1][yy1]=0,dist[xx2][yy2]=0;
vis[xx1][yy1]=1,vis[xx2][yy2]=2;
q[0]={xx1,yy1},q[1]={xx2,yy2};
int hh=0,tt=1;
while(hh<=tt)
{
auto t=q[hh++];
for (int i = 0; i < 4; i++)
{
int a=t.first+dx[i],b=t.second+dy[i];
if(a<1||a>n||b<1||b>n)continue;
if(g[a][b]!='0')continue;
if(vis[a][b]+vis[t.first][t.second]==3)
{
return dist[t.first][t.second]+dist[a][b]+1;
}
if(dist[a][b]>=0)continue;
dist[a][b]=dist[t.first][t.second]+1;
if(vis[a][b]==-1)vis[a][b]=vis[t.first][t.second];
q[++tt]={a,b};
}
}
return -1;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>g[i]+1;
}
cin>>xx1>>yy1>>xx2>>yy2;
int res=bfs();
cout<<res<<'\n';
return 0;
}P1379 八数码难题 1
#include <bits/stdc++.h>
using namespace std;
string end1="123804765";
unordered_map<string,int> umap;
queue<string> q;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int bfs(string st)
{
q.push(st);
umap[st]=0;
while(q.size())
{
auto t=q.front();
q.pop();
if(t==end1)return umap[t];
int distance=umap[t];
int a=t.find('0');
int xx1=a/3,yy1=a%3; //一维数组下标转换为二维数组下标
for (int i = 0; i < 4; i++)
{
int xx2=xx1+dx[i],yy2=yy1+dy[i];
if(xx2<0||xx2>=3||yy2<0||yy2>=3)continue;
int tmp=xx2*3+yy2;
swap(t[a],t[tmp]);
if(!umap.count(t))
{
umap[t]=distance+1;
q.push(t);
}
swap(t[a],t[tmp]);
}
}
return -1;
}
int main()
{
string start1;
cin>>start1;
int res=bfs(start1);
cout<<res;
return 0;
}#include <bits/stdc++.h>
using namespace std;
string start1;
string end1="123804765";
queue<string> q;
unordered_map<string,int> dist;
unordered_map<string,int> vis;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int bfs(string st)
{
dist[st]=0;
dist[end1]=0;
q.push(st),q.push(end1);
vis[st]=1,vis[end1]=2;
while(q.size())
{
auto t=q.front();
q.pop();
int distance=dist[t];
int flag=vis[t];
int a=t.find('0');
int xx1=a/3,yy1=a%3; //一维数组下标转换为二维数组下标
for (int i = 0; i < 4; i++)
{
int xx2=xx1+dx[i],yy2=yy1+dy[i];
if(xx2<0||xx2>=3||yy2<0||yy2>=3)continue;
int tmp=xx2*3+yy2;
swap(t[a],t[tmp]);
if(vis[t]+flag==3)
{
int res1=dist[t];
swap(t[a],t[tmp]);
int res2=dist[t];
return res1+res2+1;
}
if(!dist.count(t))
{
dist[t]=distance+1;
vis[t]=flag;
q.push(t);
}
swap(t[a],t[tmp]);
}
}
return -1;
}
int main()
{
cin>>start1;
if(start1==end1)
{
cout<<0<<'\n';
return 0;
}
int res=bfs(start1);
cout<<res;
return 0;
}————acw1101.献给阿尔吉侬的花束
————UVA439 骑士的移动
————P1135 奇怪的电梯
————P1032 字串变换
————P1825 Corn Maze S
————more and more…知道起点和终点状态的都可以用双向BFS来优化时间
作业 (上节课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值
