广度优先搜索框架
2026-07-20 11:07:55
发布于：四川
20阅读
0回复
0点赞
求赞和评论
以下仅供参考
小广告 我发现了一个好玩的广度优先搜索的动画可以辅助你理解
要用记得按题意修改
广度优先搜索
搜索顺序
#include <bits/stdc++.h>
using namespace std;
typedef pair<int ,int> pii;
int n;
int run[][2]={-1,0,0,-1,1,0,0,1,-1,-1,-1,1,1,-1,1,1};
int mp[105][105];
bool vis[105][105];
bool pa(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=n&&!vis[x][y];
}
void bfs(){
queue<pii> q;
vis[1][1]=1;
q.push({1,1});
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop();
cout<<mp[x][y]<<" ";
for(int i=0;i<4;i++){
int nx=x+run[i][0],ny=y+run[i][1];
if(pa(nx,ny)){
vis[nx][ny]=1;
q.push({nx,ny});
}
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
bfs();
return 0;
}
*最短路径
#include <bits/stdc++.h>
using namespace std;
typedef pair<int ,int> pii;
int n,m;
int run[][2]={-1,0,0,-1,1,0,0,1,-1,-1,-1,1,1,-1,1,1};
int mp[105][105];
int dis[105][105];
bool pa(int x,int y){
return x>=1&&x<=n&&y>=1&&y<=m&&!mp[x][y];
}
void bfs(){
queue<pii> q;
dis[1][1]=0;
q.push({1,1});
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop();
for(int i=0;i<4;i++){
int nx=x+run[i][0],ny=y+run[i][1];
if(pa(nx,ny)&&dis[nx][ny]==-1){
dis[nx][ny]=dis[x][y]+1;
q.push({nx,ny});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(c=='#')mp[i][j]=1;
else mp[i][j]=0;
dis[i][j]=-1;
}
}
bfs();
cout<<dis[n][m];
return 0;
}
佛祖保佑：
/*
* _ooOoo_
* o8888888o
* 88" . "88
* (| -_- |)
* O\ = /O
* ____/`---'\____
* . ' \\| |// `.
* / \\||| : |||// \
* / _||||| -:- |||||- \
* | | \\\ - /// | |
* | \_| ''\---/'' | |
* \ .-\__ `-` ___/-. /
* ___`. .' /--.--\ `. . __
* ."" '< `.___\_<|>_/___.' >'"".
* | | : `- \`.;`\ _ /`;.`/ - ` : | |
* \ \ `-. \_ __\ /__ _/ .-` / /
* ======`-.____`-.___\_____/___.-`____.-'======
* `=---='
*
* .............................................
* 佛祖保佑 永无BUG
*/
这里空空如也
有帮助，赞一个