【广度优先搜索BFS】

【BFS】

推荐视频链接
推荐好文

核心思想：层层递进，先广后深

运用手段：队列

简述：(推荐好文中有详述)

简单的说，就像石子落入水中溅起涟漪，一环一环，不断向周围扫过去。而“一环一环”就是通过队列实现的。首先将起点入队，之后取得他的坐标后便将他出队，然后根据这个坐标对其周围的点一 一扫过去，也就是一 一将他们入队，同时标记，之后都是只取队首的元素，取完后就出队，循环下去；

例题：

1.遍历

思路：
在边上的0一定不是围起来
所以只要找边上的就0，再涟漪过去

代码：

#include<bits/stdc++.h>usingnamespacestd;intn;vector<vector<int>>g(50,vector<int>(50)),s(50,vector<int>(50,0));//g表地图，s表判断数组structnode//想将一个坐标压入队列中，需要借助结构体或者二元数组{intx,y;};queue<node>qu;//队列intdx[]={1,-1,0,0};//方向数组intdy[]={0,0,-1,1};voidbfs(intx,inty){s[x][y]=1;//将起点标记qu.push((node){x,y});//让起点进队while(qu.size())//如果队列非空{intax=qu.front().x,ay=qu.front().y;//取队首元素qu.pop();//用完了就扔for(inti=0;i<4;i++)//方向{intsx=ax+dx[i],sy=ay+dy[i];if(sx>=1&&sx<=n&&sy>=1&&sy<=n&&!s[sx][sy])//不能出地图，不能是标记过的{s[sx][sy]=1;//标记qu.push((node){sx,sy});//再让这个坐标入队}}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cin>>g[i][j];}}s=g;//让判断数组先与地图相等for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i==1||j==1||i==n||j==n)//如果是在边上的0的话就一个不是围起来的0{if(g[i][j]==0&&!s[i][j])//不能是判断过的{bfs(i,j);}}}}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(s[i][j]==1&&g[i][j]==1)cout<<1<<" ";//仔细想想elseif(s[i][j]==1&&!g[i][j])cout<<0<<" ";elseif(!s[i][j]&&!g[i][j])cout<<2<<" ";}cout<<endl;}return0;}

2.最短距离

代码：

#include<bits/stdc++.h>usingnamespacestd;//bfs用的不是递归，而是循环charg[1005][1005];//地图ints[1005][1005];//不在是判断数组，而是从起点走到每个位置的最短路程structnode//依旧{intx,y;};intdx[]={1,0,0,-1};//依旧intdy[]={0,1,-1,0};intn;queue<node>qe;intx1,yz,x2,y2;voidbfs(intx,inty){g[x][y]='1';qe.push((node){x,y});while(qe.size()){intax=qe.front().x,ay=qe.front().y;qe.pop();for(inti=0;i<4;i++){intsx=ax+dx[i],sy=ay+dy[i];if(sx>=1&&sx<=n&&sy>=1&&sy<=n&&g[sx][sy]=='0'){g[sx][sy]='1';s[sx][sy]=s[ax][ay]+1;//重点在这，每格=上一格+1步qe.push((node){sx,sy});if(sx==x2&&sy==y2)return;//如果找到了就退出就行了}}}}signedmain(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cin>>g[i][j];}}cin>>x1>>yz>>x2>>y2;bfs(x1,yz);cout<<s[x2][y2];return0;}