Asteroids!_poj2225

Asteroids!_poj2225

这是一个立方体的空间的路径搜索问题，若可达输出步数，不可达输出“NO ROUTE”

一道……课后题

输入的话我是按字符输入这个空间的

然后普通的bfs，一个方向数组，一个空间数组（因为只用一次，懒的再开一个，反正标记了，就是不能走的意思）引入某大佬的函数返回值做条件判重

需要注意的是，注意它的空间x,y,z轴分别怎么表示，我是通过建模型搞的（肯定有简单的方法）

下面是代码（西加加）

#include <iostream>
#include <string>
#include <queue>
#include <cstdio>
using namespace std;
bool mapp[10][10][10];
int a,b,c,d,e,f,n;
int dir[6][3]={{0,0,1},{0,1,0},{0,0,-1},{0,-1,0},{1,0,0},{-1,0,0}};
struct point{
int x,y,z,step;
point(int xx,int yy,int zz,int ss=0):x(xx),y(yy),z(zz),step(ss){}
point(){}
};
bool judge(point ipo){//区分或与与
if(ipo.x>=n||ipo.x<0)return 0;
if(ipo.y>=n||ipo.y<0)return 0;
if(ipo.z>=n||ipo.z<0)return 0;
if(mapp[ipo.z][ipo.y][ipo.x]==1)return 0;
return 1;
}
int bfs(){
queue<point>que;
que.push(point(a,b,c));
point now;
int tstep;
while(!que.empty()){
now=que.front();
que.pop();
if(now.x==d&&now.y==e&&now.z==f){
return now.step;
}
//if(judge(now)){mapp[now.z][now.y][now.x]=1; }
mapp[now.z][now.y][now.x]=1;
int tx,ty,tz;
tstep=now.step+1;
for(int t=0;t<6;t++){
tx=now.x+dir[t][2];
ty=now.y+dir[t][1];
tz=now.z+dir[t][0];
if(judge(point(tx,ty,tz)))que.push(point(tx,ty,tz,tstep));//判断次数相等，插入删除次数少
}
}
return -1;
}
int main()
{
string str;
int i,j,k;
char ch;
while(cin >> str >> n){
for(i=0;i<n;i++)
for(j=0;j<n;j++)
for(k=0;k<n;k++)
mapp[i][j][k]=0;
getchar();
for(i=0;i<n;i++){
for(j=0;j<n;j++){
for(k=0;k<n;k++){
ch=getchar();
if(ch=='X')mapp[i][j][k]=1;
}
getchar();
}
}
scanf("%d%d%d",&a,&b,&c);
scanf("%d%d%d",&d,&e,&f);
int ans=bfs();
cin >> str;
if(ans==-1)cout << "NO ROUTE" << endl;
else cout << n << ' ' << ans << endl;
}
return 0;
}
//对应关系
//x y z
//k j i
//a b c
//d e f

原文链接:https://www.cnblogs.com/sos3210/p/12287719.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有