【广度优先搜索(一)】迷宫
2024-09-08 10:07:39
发布于：浙江
11阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N=100;
const int dx[4]{1,0,-1,0};
const int dy[4]{0,1,0,-1};
char mp[N][N];
bool vis[N][N];
int n,m;
struct node{
int x,y,step;
};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>mp[i][j];
}
}
queue<node>q;
q.push({1,1,0});
vis[1][1]=1;
while(q.size()){
node t=q.front();
q.pop();
if(t.x==n && t.y==m){
cout<<t.step;
return 0;
}
for(int i=0;i<4;i++){
int nx=t.x+dx[i];
int ny=t.y+dy[i];
if(nx<1 || nx>n || ny<1 || ny>m)continue;
if(mp[nx][ny]=='.' && vis[nx][ny]==0){
q.push({nx,ny,t.step+1});
vis[nx][ny]=1;
}
}
}
return 0;
}
全部评论 4
【广度优先搜索(二)】岛屿数量
#include<bits/stdc++.h> using namespace std; const int N=100; const int dx[]{1,0,-1,0}; const int dy[]{0,1,0,-1}; int mp[N][N]; bool vis[N][N]; int n,m; struct node{ int x,y; }; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j]; } } int cnt=0; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]==1 && !vis[i][j]){ queue<node>q; q.push({i,j}); vis[i][j]=1; cnt++; while(q.size()){ node t=q.front(); q.pop(); for(int i=0;i<4;i++){ int nx=t.x+dx[i]; int ny=t.y+dy[i]; if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny]){ continue; } if(mp[nx][ny]==0)continue; q.push({nx,ny}); vis[nx][ny]=1; } } } } } cout<<cnt; return 0; }2024-09-08 来自 浙江
0【广度优先搜索(二)】图像渲染
#include<bits/stdc++.h> using namespace std; const int N=100; const int dx[]{1,0,-1,0}; const int dy[]{0,1,0,-1}; int mp[N][N]; bool vis[N][N]; int n,m,xx,yy; struct node{ int x,y; }; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j]; } } int a; cin>>xx>>yy>>a; queue<node>q; q.push({xx,yy}); vis[xx][yy]=1; while(q.size()){ node t=q.front(); q.pop(); for(int i=0;i<4;i++){ int nx=t.x+dx[i]; int ny=t.y+dy[i]; if(nx<1 || nx>n || ny<1 || ny>m){ continue; } if(vis[nx][ny]){ continue; } if(mp[nx][ny]!=mp[xx][yy]){ continue; } mp[nx][ny]=a; q.push({nx,ny}); vis[nx][ny]=1; } } mp[xx][yy]=a; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cout<<mp[i][j]<<" "; } cout<<"\n"; } return 0; }2024-09-08 来自 浙江
0【广度优先搜索(一)】抓住那头牛
#include<bits/stdc++.h> using namespace std; bool vis[1000000]; struct node{ int x,step; }; int main(){ int n,k; scanf("%d%d",&n,&k); queue<node>q; q.push({n,0}); vis[n]=1; while(q.size()){ node t=q.front(); q.pop(); if(t.x==k){ cout<<t.step; return 0; } if(t.x-1>=0 && !vis[t.x-1]){ q.push({t.x-1,t.step+1}); vis[t.x-1]=1; } if(t.x+1<=100000 && !vis[t.x+1]){ q.push({t.x+1,t.step+1}); vis[t.x+1]=1; } if(t.x*2<=100000 && !vis[t.x*2]){ q.push({t.x*2,t.step+1}); vis[t.x*2]=1; } } return 0; }2024-09-08 来自 浙江
0
有帮助，赞一个