上次讲的DFS是一直往前走，直到无路可走的时候就返回，而BFS不一样。
BFS是广度优先搜索，顾名思义就是横着来搜索，也就是按层次来搜索，一层层来搜索。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索（DFS）那样有回退的情况，因此它不是一个递归的算法，为了实现逐层的访问，算法必须借助一个辅助队列并且以非递归的形式来实现。
BFS搜索的步骤 1、首先创建一个mp[ ]数组用来判断该位置是否被访问;
2、再创建一个队列p用来储存下一步要访问的点。
3、让起点start入队，并使该点的mp赋值为1；
4、while（！q.empty()）{…}执行搜索操作， a、取出队头元素后使队头元素出队，判断该元素是否为目标到达点； b、如果是目标点，就返回结果（一般是最短时间、最短路径）； c、如果不是目标点，就继续访问与其相邻的位置点，将可走的相邻的位置点入队，并更新mp[ ]数组直到找到目标；
模板
struct Node { int x,y; int step; };//结构体 queue<int>p;//队列p int mp[10005][10005]; int dx[]={1,0,0,-1};//方向数组 int dy[]={0,1,-1,0}; // 计算从起点 start 到终点 ed 的最近距离 int BFS(Node start, Node target) { p.push(start); //将起点加入队列 mp[stat.x][start.y]=1; while (!p.empty()) { Node temp=p.front()//取出队头元素 p.pop()//将队头元素出队 /* 将当前队列中的所有节点向四周扩散 */ for (int i = 0; i < 4; i++) { int xx=temp.x+dx[i]; int yy=temp.y+dy[i]; /* 划重点：这里判断是否到达终点 */ if (xx==target.x&&yy==target.y) return temp.step+1; if(mp[xx][yy]||越界) continue; p.push({xx,yy,temp.step+1});//将xx，yy，temp.step+1,当成结构体压入队列 mp[xx][yy]=1;//标记走过 } } }链接：https://ac.nowcoder.com/acm/problem/15136 来源：牛客网
这是一个关于二维迷宫的题目。我们要从迷宫的起点 ‘S’ 走到终点 ‘E’，每一步我们只能选择上下左右四个方向中的一个前进一格。 ‘W’ 代表墙壁，是不能进入的位置，除了墙壁以外的地方都可以走。迷宫内的 ‘D’ 代表一道上锁的门，只有在持有钥匙的时候才能进入。而 ‘K’ 则代表了钥匙，只要进入这一格，就会自动地拿到钥匙。最后 ‘.’ 则是代表空无一物的地方，欢迎自在的游荡。
本题的迷宫中，起点、终点、门跟钥匙这四个特殊物件，每一个恰好会出现一次。而且，此迷宫的四周 (最上面的一行、最下面的一行、最左边的一列以及最右边的一列) 都会是墙壁。
请问，从起点到终点，最少要走几步呢？
示例1
示例2
思路
从起点到终点一共存在两种可行性 1）起点直接到达终点， 起点 -> 终点。 2）通过 起点S -> 钥匙 -> 门-> 终点E。 最终到达终点的可行方案 1）如果 不能直接从 起点S -> 终点E ，需要考虑 获取钥匙开门的途径，如果仍然不能到达终点，则输出 -1，否则输出到达终点的最小步数。 2）如果 起点S -> 终点E 可行 ，那么 获取钥匙开门到达终点必定可行 ，此时只需比较二者步数，获得最小步数即可。
#include<bits/stdc++.h> using namespace std; int mp[505][505];//用来标记该点是否被走过 char migon[505][505];//输入 int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int H,W; struct car { int x;//行 int y;//列 int step=0;//从起点到(x,y)得最小步数; }st,ed,key,door;//定义起点，终点，钥匙，门，四个结构体； int bfs(car beg,car end) { queue<car>p;//创建一个队列储存（bfs一般都得创一个队列） p.push(beg); mp[beg.x][beg.y]=1;//将走过的做标记 while(!p.empty()) { car temp,t; temp=p.front();//获取当前格子 p.pop();//将该格子去掉 if(temp.x==end.x && temp.y==end.y) return temp.step;//如果到达终点将步数返回 for(int i=0;i<4;i++)//遍历四个方向 { int xx=temp.x+dx[i]; int yy=temp.y+dy[i]; t=temp; if(xx<0||yy<0||xx>=H||yy>=W)//越界 continue; if(mp[xx][yy]||migon[xx][yy]=='W'||migon[xx][yy]=='D')//走过的地方跳过，W是墙跳过，门跳过(后面拿到钥匙将D改成了.）； continue; t.x=xx; t.y=yy; t.step++; p.push(t); mp[xx][yy]=1; } } return -1; } int main() { cin>>H>>W; for(int i=0;i<H;i++) { for(int j=0;j<W;j++) { cin>>migon[i][j]; if(migon[i][j]=='S')//记录下起点，终点，钥匙，门的位置 st.x=i,st.y=j; else if(migon[i][j]=='E') ed.x=i,ed.y=j; else if(migon[i][j]=='K') key.x=i,key.y=j; else if(migon[i][j]=='D') door.x=i,door.y=j; } } memset(mp,0,sizeof(mp)); int ans1=bfs(st,ed);//直接从起点到终点，不开门 memset(mp,0,sizeof(mp)); int ans2=bfs(st,key);//从起点去拿钥匙 memset(mp,0,sizeof(mp)); migon[door.x][door.y]='.';//拿到钥匙将门变成点 int ans3=bfs(key,door);//拿了钥匙去开门 memset(mp,0,sizeof(mp)); int ans4=bfs(door,ed);//开完门去终点 if(ans1==-1)//不拿钥匙走不通的情况 { if(ans2==-1||ans3==-1||ans4==-1) cout<<-1<<endl; else cout<<ans2+ans3+ans4<<endl; } else cout<<min(ans1,ans2+ans3+ans4);//输出小的 return 0; }问题描述
栋栋最近开了一家餐饮连锁店，提供外卖服务。随着连锁店越来越多，怎么合理的给客户送餐成为了一个急需解决的问题。 栋栋的连锁店所在的区域可以看成是一个n×n的方格图（如下图所示），方格的格点上的位置上可能包含栋栋的分店（绿色标注）或者客户（蓝色标注），有一些格点是不能经过的（红色标注）。 方格图中的线表示可以行走的道路，相邻两个格点的距离为1。栋栋要送餐必须走可以行走的道路，而且不能经过红色标注的点。
送餐的主要成本体现在路上所花的时间，每一份餐每走一个单位的距离需要花费1块钱。每个客户的需求都可以由栋栋的任意分店配送，每个分店没有配送总量的限制。 现在你得到了栋栋的客户的需求，请问在最优的送餐方式下，送这些餐需要花费多大的成本。
输入格式
输入的第一行包含四个整数n, m, k, d，分别表示方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量。 接下来m行，每行两个整数xi, yi，表示栋栋的一个分店在方格图中的横坐标和纵坐标。 接下来k行，每行三个整数xi, yi, ci，分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。（注意，可能有多个客户在方格图中的同一个位置） 接下来d行，每行两个整数，分别表示每个不能经过的点的横坐标和纵坐标。
输出格式
输出一个整数，表示最优送餐方式下所需要花费的成本。
样例输入
10 2 3 3 1 1 8 8 1 5 1 2 3 3 6 7 2 1 2 2 2 6 8
样例输出
29
评测用例规模与约定
前30%的评测用例满足：1<=n <=20。 前60%的评测用例满足：1<=n<=100。 所有评测用例都满足：1<=n<=1000，1<=m, k, d<=n^2。可能有多个客户在同一个格点上。每个客户的订餐量不超过1000，每个客户所需要的餐都能被送到。
#include<bits/stdc++.h> using namespace std; int n,m,k,d; int mp[1005][1005]; int w[1005][1005]; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; struct car { int x,y; int step; }; queue<car>p; int bfs() { long long sum=0,cnt=0;//sum是记录总花费，cnt是记录已经送了几家客户 while(!p.empty()) { car temp=p.front(); p.pop(); for(int i=0; i<4; i++) { int xx=temp.x+dx[i]; int yy=temp.y+dy[i]; int st=temp.step+1; if(!mp[xx][yy]&&xx>0&&xx<=n&&yy>0&&yy<=n) { mp[xx][yy]=1; if(w[xx][yy]!=0) {//走到客户时 sum+=st*w[xx][yy]; if(++cnt==k) return sum;//全部客户送完 } p.push({xx,yy,st}); } } } } int main() { int x,y,c; cin>>n>>m>>k>>d; for(int i=1;i<=m;i++) { cin>>x>>y; mp[x][y]=1; p.push({x,y,0});//将每个店当起点压入队列 } for(int i=1;i<=k;i++) { cin>>x>>y>>c; w[x][y]=c;//将客户的位置和订餐量记录下来 } for(int i=1;i<=d;i++) { cin>>x>>y; mp[x][y]=1;//将不能走的地方标记为走过 } cout<<bfs()<<endl; return 0; }https://www.luogu.com.cn/problem/P1443
来源: 洛谷
题目描述
有一个n × \times ×m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
一行四个数据，棋盘的大小和马的坐标
输出格式
一个n × \times ×m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
输入
3 3 1 1输出
0 3 2 3 -1 1 2 1 4 #include<bits/stdc++.h> using namespace std; int n,m,x,y; int dx[]={1,2,2,-1,-2,-2,1,-1}; int dy[]={2,1,-1,2,1,-1,-2,-2}; int mp[1005][1005]; int a[1005][1005];//用来记录起点到每一个点的步数 struct car { int x,y; }; queue<car>p; void bfs(car st) { a[st.x][st.y]=0; car temp; p.push(st); mp[st.x][st.y]=1; while(!p.empty()) { temp=p.front(); p.pop(); for(int i=0;i<8;i++)//遍历8个方向 { int xx=temp.x+dx[i]; int yy=temp.y+dy[i]; if (xx<1||yy<1||xx>n||yy>m||mp[xx][yy]) continue; mp[xx][yy]=1; p.push({xx,yy}); a[xx][yy]=a[temp.x][temp.y]+1; } } } int main() { cin>>n>>m>>x>>y; memset(a,-1,sizeof(a)); bfs({x,y}); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%-5d",a[i][j]); } cout<<endl; } return 0; }