关于此题最短路的问题
查看原帖
关于此题最短路的问题
444195
caramel_qwq楼主2022/5/16 19:41

以下是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
2022/5/16 19:41
加载中...