AKSZ-广度优先搜索(BFS)
2024-09-16 15:19:40
发布于：广东
31阅读
0回复
0点赞
前情提要
- 回溯：递归
- 剪枝
- 可行性剪枝
- 自由性剪枝
bfs例题——迷宫
题目描述
一个迷宫由 R 行 C 列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。
输入格式
第一行是两个整数，
R 和 C(1≤R,C≤40)，代表迷宫的长和宽。
接下来是 R 行，每行 C 个字符，代表整个迷宫。
空地格子用.表示，有障碍物的格子用 #表示。
迷宫左上角和右下角都是.。
输出格式
输出从左上角走到右下角最小移动的步数。计算步数不包含起点。
输入输出样例
输入#1
5 5
..###
#....
#.#.#
#.#.#
#.#..
输出#1
8
说明/提示
数据范围：(1≤R,C≤40)
样例说明：
移动路径为
[1,1]−>[1,2]−>[2,2]−>[2,3]−>[2,4]−>[3,4]−>[4,4]−>[5,4]−>[5,5]，一共花费8步
参考代码如下：
#include<bits/stdc++.h>
using namespace std;
//太模板化
const int N=45;
int n,m;
char s[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};//方向数组
bool vis[N][N];
//状态 在哪个点，目前使用step步数
//结构体定义状态
struct node{
int x,y;
int step;
};
void bfs(){
//先让出发点入队
//维护这个队列 ->扩展我们的状态
queue<node>q;//状态队列
q.push(node{0,0,0});//将0,0,0状态入队
vis[0][0]=1;
while(!q.empty()){//队列非空，更新状态
node tmp=q.front();//去除队列头
q.pop();//出队
if(tmp.x==n-1&&tmp.y==m-1){
cout<<tmp.step<<endl;
return;//第一个找到
}
for(int i=0;i<4;++i){
int tx=tmp.x+dx[i];//下一步x，y坐标
int ty=tmp.y+dy[i];
if(tx<0||tx>=n||ty<0||ty>=m)continue;//越界
if(vis[tx][ty])continue;//每个点只能访问一次
if(s[tx][ty]=='#')continue;
vis[tx][ty]=1;//访问
q.push(node{tx,ty,tmp.step+1});//新状态入队
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)cin>>s[i][j];
}
bfs();
return 0;
}
bfs练习
图像渲染
#include<bits/stdc++.h>
using namespace std;
//太模板化
const int N=55;
int n,m;
int s[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};//反向数字
bool vis[N][N];int x,y,z,t;
//状态 在哪个点，目前使用step步数
//结构体定义状态
struct node{
int x,y;
//int step;
};
void bfs(){
//先让出发点入队
//维护这个队列 ->扩展我们的状态
queue<node>q;//状态队列
q.push(node{x,y/*,0*/});//将0,0,0状态入队
vis[1][1]=0;
while(!q.empty()){//队列非空，更新状态
node tmp=q.front();//去除队列头
q.pop();//出队
//if(tmp.x==n-1&&tmp.y==m-1){
// cout<<tmp.step<<endl;
// return;//第一个找到
//}
for(int i=0;i<4;++i){
int tx=tmp.x+dx[i];//下一步x，y坐标
int ty=tmp.y+dy[i];
if(tx<1||tx>n||ty<1||ty>m)continue;//越界
if(vis[tx][ty])continue;//每个点只能访问一次
if(s[tx][ty]!=t)continue;
vis[tx][ty]=1;//访问
s[tx][ty]=z;
q.push(node{tx,ty/*,tmp.step+1*/});//新状态入队
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)cin>>s[i][j];
}
cin>>x>>y>>z;
t=s[x][y];
s[x][y]=z;
bfs();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j)cout<<s[i][j]<<" ";
cout<<endl;
}
return 0;
}
岛屿数量
#include<bits/stdc++.h>
using namespace std;
//太模板化
const int N=110;
int n,m,cnt;
char s[N][N];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};//方向数组
bool vis[N][N];
//状态 在哪个点，目前使用step步数
//结构体定义状态
struct node{
int x,y;
//int step;
};
void bfs(int xx,int yy){
//先让出发点入队
//维护这个队列 ->扩展我们的状态
queue<node>q;//状态队列
q.push(node{xx,yy/*,0*/});//将0,0,0状态入队
vis[xx][yy]=1;
while(!q.empty()){//队列非空，更新状态
node tmp=q.front();//去除队列头
q.pop();//出队
//if(tmp.x==n-1&&tmp.y==m-1){
// cout<<tmp.step<<endl;
// return;//第一个找到
//}
for(int i=0;i<4;++i){
int tx=tmp.x+dx[i];//下一步x，y坐标
int ty=tmp.y+dy[i];
if(tx<0||tx>=n||ty<0||ty>=m)continue;//越界
if(vis[tx][ty])continue;//每个点只能访问一次
if(s[tx][ty]=='0')continue;
vis[tx][ty]=1;//访问
q.push(node{tx,ty/*,tmp.step+1*/});//新状态入队
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)cin>>s[i][j];
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(s[i][j]=='1'&&!vis[i][j]){
bfs(i,j);
++cnt;
}
}
}
cout<<cnt;
return 0;
}
有帮助，赞一个