AKSZ - BFS
2024-05-19 18:09:18
发布于：广东
14阅读
0回复
0点赞
无他，惟模板尔。
//以下代码实际实现效果为连通块，最短路加上注释掉的代码
#include<iostream>
#include<queue>
using namespace std;
const int maxn=45;
int n,m,dx[]={-1,0,1,0},dy[]={0,1,0,-1}/*方向数组*/,vis[maxn][maxn]/*染色，防止重复访问*/;
int s[maxn][maxn];//要查找的数组
struct node{//要扩张的格子
int x,y;
//可依需求加入步数
};
void bfs(int _x,int _y/*,int x_,int y_//终点坐标*/){
queue<node>q;//用于存放要扩张的格子下标
q.push(node{_x,_y});//起始格子
vis[_x][_y]=1;//标记起始格子
while(q.size()){//搜索至没有可扩张的格子（队列为空）
node tmp=q.front();//当前格子
q.pop();
/*
if(tmp._x==x_&&tmp._y==y_){//判断是否到终点
cout<<tmp.step;//输出步数
return ;
}
*/
for(int i=0;i<4;i++){
int tx=tmp.x+dx[i],ty=tmp.y+dy[i];//当前格子坐标
if(tx<0||tx>=n||ty<0||ty>=m/*特判越界*/||vis[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);//关闭同步流
int x,y/*,a,b*/;
cin>>x>>y/*>>a>>b*/;
bfs(x,y/*,a,b*/);//参数为起始坐标和终点坐标（如果最短路的话）
return 0;
}
注释足够清楚了吧…………
有帮助，赞一个