BFS模板题

**

hdu1240 Asteroids!

**
BFS模板题

#include <string.h>
#include <stdio.h>
#include <queue>
using namespace std;
char map[20][20][20];
int vis[20][20][20];
int n;
int sx,sy,sz;
int ex,ey,ez;
int tx[] = {1,-1,0,0,0,0};//六个方向
int ty[] = {0,0,1,-1,0,0};
int tz[] = {0,0,0,0,1,-1};
struct node
{
int x,y,z,step;
};
int check(int x,int y,int z)//判断是否越界或者已经走过
{
if(x<0 || y<0 || z<0 || x>=n || y>=n || z>=n || vis[x][y][z] )
return 0;
return 1;
}
int bfs(int x,int y,int z)//广度优先搜索终点
{
int i;
queue<node> Q;
node a,next;
a.x = x;
a.y = y;
a.z = z;
a.step = 0;
vis[x][y][z] = 1;
Q.push(a);
while(!Q.empty())
{
a = Q.front();
Q.pop();
if(a.x == ex && a.y == ey && a.z == ez)
return a.step;
for(i = 0;i<6;i++)
{
next = a;
next.x+=tx[i];
next.y+=ty[i];
next.z+=tz[i];
if(check(next.x,next.y,next.z))
{
next.step++;
vis[next.x][next.y][next.z] = 1;
Q.push(next);
}
}
}
return -1;
}
int main()
{
char s[10];
int i,j,k;
while(~scanf("%s%d",s,&n))
{
for(i = 0;i<n;i++)
for(j = 0;j<n;j++)
scanf("%s",map[i][j]);
scanf("%d%d%d%d%d%d",&sx,&sy,&sz,&ex,&ey,&ez);//s为起始，e为终点
scanf("%s",s);
int ans = bfs(sx,sy,sz);
if(ans>=0)
printf("%d %dn",n,ans);
else
printf("NO ROUTEn");
}
return 0;
}

最后

以上就是复杂山水为你收集整理的BFS模板题的全部内容，希望文章能够帮你解决BFS模板题所遇到的程序开发问题。

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