结构体+队列+BFS

Dungeon Master

注：结构体中变量跟全局变量不要用相同的字符

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int x2,y2,z2;
int h,w,l;
char map[35][35][35];
int visit[35][35][35];
int dir[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
struct node{
int x,y,z;
int num;
};
void bfs()
{
queue <node> q;
node t,end,start;
t.x=x2; t.y=y2; t.z=z2;
t.num=0;
visit[x2][y2][z2]=1;
q.push(t);
while(!q.empty())
{
start = q.front();
q.pop();
int x1=start.x;
int y1=start.y;
int z1=start.z;
int count=start.num;
if(map[x1][y1][z1]=='E')
{
cout<<"Escaped in "<<count<<" minute(s)."<<endl;
return;
}
for(int i=0;i<6;i++)
{
int xx=end.x=x1+dir[i][0];
int yy=end.y=y1+dir[i][1];
int zz=end.z=z1+dir[i][2];
end.num=count+1;
if(xx<1 || yy<1 || zz<1 || xx>l || yy>w || zz>h)continue;
if(map[xx][yy][zz]!='#' && !visit[xx][yy][zz])
{
visit[xx][yy][zz]=1;
q.push(end);
}
}
}
cout<<"Trapped!"<<endl;
}
int main()
{
while(cin>>l>>w>>h)
{
if(l==0&&w==0&&h==0)break;
for(int i=1;i<=l;i++)
for(int j=1;j<=w;j++)
for(int k=1;k<=h;k++)
{
cin>>map[i][j][k];
if(map[i][j][k]=='S')
{
x2=i;y2=j;z2=k;
}
}
memset(visit,0,sizeof(visit));
bfs();
}
return 0;
}

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
//node代表位置 
struct node{
int x;
int y;
};
//存储的内容 
char a[150][150];
int v[150][150];
//矩阵的宽高width、height 
int w,h;
//移动的4个方向 
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
void bfs(node m,node n)
{
//初始化 
memset(v,0,sizeof(v));
//start为下面的循环中的起始点 end为走一步后所到达的点 
node start,end;
queue<node> q;
//将初始位置加入队列 
q.push(m);
//标记初始位置的点为走了一步 （为什么不是 0 呢？因为 0 默认是未经过的点，是1的话只要最好减 1 就好了） 
v[m.x][m.y]=1;
//疯狂走 获取当前位置并使其出队列 寻找下一个可以走且未经过的位置 循环 
while(!q.empty()){
//获取当前位置 
start=q.front();
//队列
q.pop();
for(int i=0;i<=3;i++)
{
//xx yy 是移动后的方向 
int xx=start.x+dir[i][0];
int yy=start.y+dir[i][1];
//判断是否越界，下个位置是否可以走 
if(xx<=0||yy<=0||xx>w||yy>h||a[xx][yy]=='#')
continue;
//！=0说明这个点没走过 ，可以走 
if(!v[xx][yy])
{
end.x=xx;
end.y=yy;
//end 加入队列 作为下一次循环的起始点 
q.push(end);
//记录此时所走过的次数 
v[xx][yy]=v[start.x][start.y]+1;
}
if(xx==n.x&&yy==n.y)return;
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
int n;
cin>>n;
node start,end;
while(n--)
{
//输入数据 
cin>>w>>h;
for(int i=1;i<=w;i++)
for(int j=1;j<=h;j++)
{
cin>>a[i][j];
if(a[i][j]=='S'){
//标记开始位置 
start.x=i;start.y=j;
}else if(a[i][j]=='E'){
//标记结束位置 
end.x=i;end.y=j;
}
}
bfs(start,end);
cout<<v[end.x][end.y]-1<<endl;
}
return 0;
}

最后

以上就是大方飞机为你收集整理的简单搜索（BFS）结构体+队列+BFS的全部内容，希望文章能够帮你解决简单搜索（BFS）结构体+队列+BFS所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。