首页 > 代码库 > HDU 1240——Asteroids!(三维BFS)POJ 2225——Asteroids
HDU 1240——Asteroids!(三维BFS)POJ 2225——Asteroids
普通的三维广搜,需要注意的是输入:列,行,层
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define M 11 using namespace std; int dir[6][3]={{0,1,0},{0,-1,0},{1,0,0},{-1,0,0},{0,0,1},{0,0,-1}};//6个方向 int vis[M][M][M]; char map[M][M][M]; int n,m,p,sx,sy,sz,ex,ey,ez; bool ck(int x,int y,int z) { if(x>=0&&x<n&&y>=0&&y<n&&z>=0&&z<n&&!vis[z][x][y]&&map[z][x][y]=='O') return true; return false; } struct node { int x,y,z,st; }; void bfs( ) { if(sx==ex&&sy==ey&&sz==ez){ cout<<n<<" "<<0<<endl; return ; } memset(vis,0,sizeof vis); queue<node> q; node a,b; a.z=sz,a.x=sx,a.y=sy,a.st=0; vis[sz][sx][sy]=1; q.push(a); while(!q.empty()){ a=q.front(),q.pop(); for(int i=0;i<6;++i){ b.x=a.x+dir[i][0]; b.y=a.y+dir[i][1]; b.z=a.z+dir[i][2]; b.st=a.st+1; if(!ck(b.x,b.y,b.z)) continue; if(b.x==ex&&b.y==ey&&b.z==ez){ cout<<n<<" "<<b.st<<endl; return; } vis[b.z][b.x][b.y]=1; q.push(b); } } printf("NO ROUTE\n"); return ; } int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); while(scanf("START %d",&n)!=EOF){ for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ scanf("%s",map[i][j]); } } scanf("%d%d%d %d%d%d",&sy,&sx,&sz,&ey,&ex,&ez); char str[10]; cin>>str; getchar(); bfs( ); } return 0; }<span style="color:#3333ff;"> </span>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。