广搜模板（万能）
2025-01-10 11:37:13
发布于：北京
5阅读
0回复
0点赞
1，起点标记并入队（涉及到最短路，起点最短路为零）
2，队列不为空
2.1取队首并出队
2.2 在这个位置有很多操作，例如判断是否搜索到答
案，或对当前搜索到的点求最大值最小值等等。
2.3遍历a的邻接点“非越界”“可以走”“未被标记”，
就把邻接点标记并入队（涉及到最短路，邻接点最短路=a的最短路+1）。
3，队列空退出，若没有找到答案，reutrn -1；
#include<iostream>
#include<queue>
using namespace std;
struct node{
int x,y,step;
};
queue<node> q;
int r,c;
char s[105][105];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool flag[105][105];
int xx,yy;
int main(){
cin>>r>>c;
for(int i=1;i<=r;i++){
cin>>(s[i]+1);
}
node a;
q.push({1,1,0});
flag[1][1]=1;
while(!q.empty()){
a=q.front();
q.pop();
if(a.x==r&&a.y==c){
cout<<a.step;
return 0;
}
for(int i=0;i<=3;i++){
xx=dx[i]+a.x;
yy=dy[i]+a.y;
if(1<=xx&&xx<=r&&1<=yy&&yy<=c&&s[xx][yy]!='#'&&flag[xx][yy]==0){
flag[xx][yy]=1;
q.push({xx,yy,a.step+1});
}
}
}
return 0;
}
据要求修改
这里空空如也
有帮助，赞一个