以下是BFS的摘录,问题是我的最短路出来是9步,但是题目中是11步,请问少的那两步分别是少在哪?(下面有过程变量摘录)
const int dx[8]={-1,1,0,0};
const int dy[8]={0,0,-1,1};
const int dz[8]={0,-1,1};
struct point{
int z,x,y,step;
};
int sx,sy,sz,ex,ey,ez;
char a[38][38][38];
bool v[38][38][38];
void bfs(){
queue<point> q;
q.push({sz,sx,sy,0});
v[sz][sx][sy]=1;
while(!q.empty()){
point u=q.front();
q.pop();
if(u.x==ex&&u.y==ey&&u.z==ez){
ans=u.step;
break;
}
for(int k=0;k<3;k++){
for(int i=0;i<4;i++){
int nx=u.x+dx[i],ny=u.y+dy[i],nz=u.z+dz[k];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&nz>=1&&nz<=h){
if(v[nz][nx][ny]==0){
q.push({nz,nx,ny,u.step+1});
v[nz][nx][ny]=1;
}
}
}
}
}
return ;
}
以下是过程变量(输出xyz和step)
(1,1,1)-0
(1,2,1)-1
(1,1,2)-1
(1,3,1)-2
(1,1,3)-2
(1,1,4)-3
(1,1,5)-4
(1,2,5)-5
(1,3,5)-6
(1,3,4)-7
(2,4,5)-7
(1,4,4)-8
(2,4,4)-8
(2,3,3)-8
(2,4,3)-9
(3,4,5)-9