原题单链接：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
#define x first
#define y second
using namespace std;
const int N = 110;
typedef pair pii;
int n,m;
int g[N][N];
int dist[N][N];
queue 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 n||bm) 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> g[i][j];
}
}
int res=bfs(1,1);
cout 若打不开这个题就看这个 [P1746 离开中山路](https://www.luogu.com.cn/problem/P1746)
代码见下文。
# 习题课
### 热身 - 简单迷宫问题
#### [P1746 离开中山路](https://www.luogu.com.cn/problem/P1746) 1
```cpp
#include
using namespace std;
typedef pair pii;
const int N=1010;
int n;
int mx1,my1,mx2,my2;
char g[N][N];
int dist[N][N];
int res;
queue 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;in||bn)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>g[i][j];
}
}
// for(int i=1;i>g[i]+1;
// }
cin>>mx1>>my1;
cin>>mx2>>my2;
res=bfs(mx1,my1);
cout
using namespace std;
typedef pair 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(hhn||bm)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
using namespace std;
typedef pair 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(hhn||bm)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
using namespace std;
typedef pair 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(hhn+1||bn+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>g[i][j];
}
}
bfs(0,0);
for(int i=1;i
using namespace std;
typedef pair 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=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;i301||b301)continue;
fire[a][b]=min(t,fire[a][b]);
}
}
int res=bfs();
cout
using namespace std;
typedef pair 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 m || 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 > high[i][j];
}
}
for (int i = 1; i > flag[i][j];
if (flag[i][j] == 1)
{
cnt_flag++;
}
}
}
for (int i = 1; i
using namespace std;
int g[2][4];
unordered_map dist;
unordered_map> pre;
queue q;
void set1(string state)
{
for (int i = 0; i = 0; i--, j++)
{
g[1][i] = state[j];
}
}
string get1()
{
string res;
for (int i = 0; i = 0; i--)
{
res += g[1][i];
}
return res;
}
// 交换上下两行，A
string move0(string state)
{
set1(state);
for (int i = 0; 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 > x)
{
end += char(x + '0');
}
int res = bfs(start, end);
cout
using namespace std;
typedef pair pii;
const int N = 510;
int n,m,xx1,yy1,xx2,yy2;
char g[N][N];
int dist[N][N];
deque 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 =n||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 > g[i];
}
memset(dist,-1,sizeof(dist));
q.clear();
cin>>xx1>>yy1>>xx2>>yy2;
int res =bfs(xx1,yy1);
cout
using namespace std;
typedef pair 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(hhn||bn)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>g[i]+1;
}
cin>>xx1>>yy1>>xx2>>yy2;
int res=bfs();
cout
using namespace std;
string end1="123804765";
unordered_map umap;
queue 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 =3||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
```cpp
#include
using namespace std;
string start1;
string end1="123804765";
queue q;
unordered_map dist;
unordered_map 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 =3||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
## 作业 (上节课DFS过不去, 这节课可以用BFS试一试~)
#### [P1135 奇怪的电梯](https://www.luogu.com.cn/problem/P1135) dfs暴力过不去
### **Flood fill** --- **找连通块**
#### [P1596 Lake Counting S](https://www.luogu.com.cn/problem/P1596)
#### [P1451求细胞数量](https://www.luogu.com.cn/problem/P1451)
#### [P1331 海战](https://www.luogu.com.cn/problem/P1331)
#### [P1767 家族](https://www.luogu.com.cn/problem/P1767)
#### [SP15436 UCV2013H - Slick](https://www.luogu.com.cn/problem/SP15436)
### 迷宫问题
#### [P1683 入门](https://www.luogu.com.cn/problem/P1683)
#### [P1605 迷宫](https://www.luogu.com.cn/problem/P1605)
#### [P1443 马的遍历](https://www.luogu.com.cn/problem/P1443)
#### [P1747 好奇怪的游戏](https://www.luogu.com.cn/problem/P1747)
#### [P2298 Mzc和男家丁的游戏](https://www.luogu.com.cn/problem/P2298)
# 关于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值