三维 A*：26 邻域与严格禁止穿角
题目
求体素栅格起点至终点的最短路径长度。26 邻域边长为 。一次移动的每个非空轴子集所对应的中间体素必须都空闲（面、棱、体对角均禁止穿角）。使用欧氏启发式 实现 A*；只输出长度，不限定路径。离散栅格不代表真实载具安全走廊。
输入
，随后起点和终点的三维坐标，以及 行障碍坐标。，所有坐标合法。
输出
最短长度；端点被占据或不可达输出 。
示例
输入
4 4 4 24
0 0 0
3 3 3
0 1 2
0 2 1
0 2 2
0 2 3
0 3 2
1 0 2
1 1 1
1 1 3
1 2 2
1 2 3
2 1 0
2 1 1
2 3 0
2 3 1
2 3 2
2 3 3
3 0 0
3 0 1
3 0 3
3 1 0
3 1 1
3 2 0
3 3 1
3 3 2
期望输出
7.146264369941973
在线 C++17 练习
在浏览器编译运行，代码不上传；首次下载约 28 MB。
尚未运行
运行环境
Clang 22 / C++17 / WASI，支持本题所需标准库；不支持线程、C++ 异常或任意宿主系统访问。每例 2 秒、256 MiB 线性内存、64 KiB 输出；编译器另占浏览器内存，不适合低内存设备。初次加载最多等待 120 秒，可随时停止。
草稿保存在本浏览器。测试公开，属于本地自测而非防作弊竞赛判题；参考解答不参与运行。所有运行资产均由本站提供。
编译器来源与开源许可参考实现（完成后再展开）
对照自己的推导，检查状态更新顺序、边界条件与单位，而不只比较最终输出。
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <tuple>
#include <limits>
using namespace std;
// Reference implementation: optional; solve the starter before opening.
int main() {
cout << setprecision(17);
int X,Y,Z,B;
cin>>X>>Y>>Z>>B;
array<int,3>s,g;
for(int&i:s)cin>>i;
for(int&i:g)cin>>i;
auto idx=[&](int x,int y,int z) {
return (x*Y+y)*Z+z;
};
vector<bool>block(X*Y*Z,false);
while(B--) {
int x,y,z;
cin>>x>>y>>z;
block[idx(x,y,z)]=true;
}
auto free=[&](int x,int y,int z) {
return x>=0&&x<X&&y>=0&&y<Y&&z>=0&&z<Z&&!block[idx(x,y,z)];
};
if(!free(s[0],s[1],s[2])||!free(g[0],g[1],g[2])) {
cout<<-1;
return 0;
}
auto h=[&](int x,int y,int z) {
return sqrt(double((x-g[0])*(x-g[0])+(y-g[1])*(y-g[1])+(z-g[2])*(z-g[2])));
};
using Q=tuple<double,double,int,int,int>;
priority_queue<Q,vector<Q>,greater<Q>>pq;
vector<double>dist(X*Y*Z,1e99);
dist[idx(s[0],s[1],s[2])]=0;
pq.emplace(h(s[0],s[1],s[2]),0,s[0],s[1],s[2]);
while(!pq.empty()) {
auto[f,c,x,y,z]=pq.top();
pq.pop();
if(c>dist[idx(x,y,z)])continue;
if(array<int,3> {
x,y,z
}
==g) {
cout<<c;
return 0;
}
for(int dx=-1;dx<=1;dx++)for(int dy=-1;dy<=1;dy++)for(int dz=-1;dz<=1;dz++) {
if(dx==0&&dy==0&&dz==0)continue;
bool ok=true;
for(int a=0;a<=1;a++)for(int b=0;b<=1;b++)for(int e=0;e<=1;e++) {
if(!free(x+a*dx,y+b*dy,z+e*dz))ok=false;
}
if(!ok)continue;
int xx=x+dx,yy=y+dy,zz=z+dz;
double nd=c+sqrt(double(dx*dx+dy*dy+dz*dz));
if(nd<dist[idx(xx,yy,zz)]) {
dist[idx(xx,yy,zz)]=nd;
pq.emplace(nd+h(xx,yy,zz),nd,xx,yy,zz);
}
}
}
cout<<-1;
}