C++————广度优先搜索(基础)
广度优先搜索（Breadth-First Search，简称 BFS）是一种用于遍历或搜索树或图的算法。
原理
BFS 从给定的起始节点开始，逐层地访问图或树中的节点。具体来说，它先访问起始节点的所有邻接节点（即距离起始节点为 1 的节点），然后再依次访问这些邻接节点的邻接节点（距离起始节点为 2 的节点），以此类推，直到遍历完所有可达节点或找到目标节点。
广度优先搜索是一种队列式搜索，特点就是具有迭代和遍历的属性，本文以二维数组为例。
广度优先搜索在基本情况下（即无边界）就像洪水蔓延一样，接下来以Minecraft（我的世界）演示。
假设绿宝石块的地方是搜索原点，每种不同的方块代表一代。
搜索的基本单位是搜索点和与其距离1的相邻格，也就是绿宝石和金块组成的单位（绿宝石块和他的上下左右）
我的世界模拟广度优先搜索
算法步骤
- 初始化：
- 创建一个队列（Queue），用于存储待访问的节点。
- 创建一个访问标记数组（Visited Array），用于记录每个节点是否已经被访问过。
- 将起始节点加入队列，并标记为已访问。
- 循环处理队列：
- 当队列不为空时，取出队列的头部节点。
- 处理该节点（例如，打印节点信息、检查是否为目标节点等）。
- 遍历该节点的所有邻接节点，如果邻接节点未被访问过，则将其加入队列，并标记为已访问。
- 结束条件：
- 当队列为空时，说明所有可达节点都已被访问，算法结束。
技巧：
1.记忆化：
每次搜索的都是当前的上下左右，那么如果仅是单纯的重复搜索，那么一个节点可能会被访问无数次，所有可以通过改变数组元素，或者建立访问数组。
2.建立方向数组：
分别代表上下左右xx=x+X[i]，yy=y+Y[i]。
int X[4]={-1,1,0,0},Y[4]={0,0,-1,1};3.使用<queue>和结构体
建立一个放置坐标队列，先进先出的队列能保证按照层次搜索。
struct node {
int x;
int y;
};
queue<node> q;4.合法性判断 ：
只有不越界并且符合的坐标才能入队。
代码实现：
自创一道模版题，填坑游戏，0代表平坦，1代表是坑，相连的1属于一个坑，问一共要填多少个坑。
遍历整个数组，检测到坑，就把这一整个坑填起来，记录坑的总数。
#include<iostream>
#include<queue>
using namespace std;
struct node {
int x;
int y;
};
queue<node> q;
int X[4]={-1,1,0,0},Y[4]={0,0,-1,1};
int a[4][8]={
{0,0,1,1,0,0,0,0},
{0,0,0,1,1,1,0,0},
{1,1,0,1,1,0,1,1},
{0,0,0,0,1,0,1,1}
};
int main() {
int ans=0;
for (int j = 0; j < 4; ++j) {
for (int k = 0; k < 8; ++k) {
if(a[j][k]==1) {q.push({j,k});++ans;}
while(!q.empty()) {
int x=q.front().x;
int y=q.front().y;
q.pop();
for(int i=0;i<4;++i) {
int xx=x+X[i];
int yy=y+Y[i];
if(xx>=0 && xx<4 && yy>=0 && yy<8&&a[xx][yy]==1) {
q.push({xx,yy});
a[xx][yy]=0;
}
}
}
}
}
cout<<ans<<endl;
return 0;
}例题进阶：
1.洛谷P1162填涂颜色
题目大意：1圈内的0改成2.
方法：改圈内的会很麻烦，所有我们改圈外的，初始v数组，再建立一个ans数字存最终答案
这个圈最大的情况就是边界，我们把边界上是0的点都入队，这样就能找到圈外。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node {
int x,y;
};
queue<node> q;
int n,a,b,X[4]={-1,+1,0,0},Y[4]={0,0,-1,1};//上下左右
int main() {
cin>>n;
vector<vector<int>> v(n,vector<int>(n,0));
vector<vector<int>> ans(n,vector<int>(n,0));
for(int i=0,check=1;i<n;i++) {
for(int j=0;j<n;j++) {
cin>>v[i][j];
ans[i][j]=v[i][j];
}
}
for(int i=0;i<n;i++) {
if(v[i][0]==0) {q.push({i,0});v[i][0]=1;}
if(v[i][n-1]==0) {q.push({i,n-1});v[i][n-1]=1;}
if(v[0][i]==0) {q.push({0,i});v[0][i]=1;}
if(v[n-1][i]==0) {q.push({n-1,i});v[n-1][i]=1;}
}
while(!q.empty()) {
int x=q.front().x,y=q.front().y;
q.pop();
for(int i=0;i<4;i++) {
int xx=x+X[i],yy=y+Y[i];
if(xx>=0&&xx<n&&yy>=0&&yy<n&&v[xx][yy]==0) {
q.push({xx,yy});
v[xx][yy]=1;
}
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(v[i][j]==0) {ans[i][j]=2;}
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
return 0;
}2.洛谷P1443马的遍历
题目大意：象棋中马的规则，判断几部能到达某个格子
由于我们的广度优先搜索bfs是逐层的，处理这种几步的题很方便，到达不了的地方是-1，干脆从初始化就是-1，然后到达的地方进行记忆化，每层+1。
（X[],Y[]是很灵活的）
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node {
int x, y;
};
queue<node> q;
int n, m, x, y, X[8] = {-1, 1, -1, 1, -2, 2, -2, 2}, Y[8] = {2, 2, -2, -2, 1, 1, -1, -1};
int main() {
cin >> n >> m >> x >> y;
vector<vector<int> > v(n + 1, vector<int>(m + 1, -1));
v[x][y] = 0;
q.push({x, y});
while (!q.empty()) {
x = q.front().x;
y = q.front().y;
q.pop();
for (int i = 0; i < 8; i++) {
int xx = x + X[i];
int yy = y + Y[i];
if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && v[xx][yy] == -1) {
q.push({xx, yy});
v[xx][yy] = v[x][y] + 1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << v[i][j] << " ";
}
cout << endl;
}
return 0
}