题意：
在n ∗ n ∗ n的立方体中，有m个范围有障碍物，即每个范围里对于满足x 1 < = x < = x 2 , y 1 < = y < = y 2 , z 1 < = z < = z 2的坐标为障碍物。
问从起点到终点的最短距离
思路：
由于坐标系为三维的空间，可以将障碍物标记为1，借助三维前缀和计算出每个点能否可以通过。
再用b f s求最短距离。
关于三维前缀和的博客：点击跳转
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn = 1e5 + 10; struct node{ int x,y,z; }; int n,m,b[110][110][110],dis[110][110][110],a[110][110][110]; bool vis[110][110][110]; node S,T; int nx[]={1,-1,0,0,0,0}; int ny[]={0,0,1,-1,0,0}; int nz[]={0,0,0,0,1,-1}; bool check(int x,int y,int z){ if(x>=1&&x<=n&&y>=1&&y<=n&&z>=1&&z<=n) return 1; return 0; } int bfs(){ memset(dis,0x3f,sizeof dis); queue<node>q; q.push(S);dis[S.x][S.y][S.z]=0; while(!q.empty()){ node t=q.front();q.pop(); int x=t.x,y=t.y,z=t.z; if(x==T.x&&y==T.y&&z==T.z) return dis[x][y][z]; for(int i=0;i<6;i++){ int xx=x+nx[i],yy=y+ny[i],zz=z+nz[i]; if(check(xx,yy,zz)&&b[xx][yy][zz]==0&&dis[xx][yy][zz]>dis[x][y][z]+1){ dis[xx][yy][zz]=dis[x][y][z]+1; q.push({xx,yy,zz}); } } } return -1; } int main() { int _=read; while(_--){ n=read,m=read; memset(b,0,sizeof b);memset(a,0,sizeof a); rep(i,1,m){ int x1=read,y1=read,z1=read,x2=read,y2=read,z2=read; a[x1][y1][z1]--; a[x1][y1][z2+1]++; a[x1][y2+1][z1]++; a[x2+1][y1][z1]++; a[x1][y2+1][z2+1]--; a[x2+1][y1][z2+1]--; a[x2+1][y2+1][z1]--; a[x2+1][y2+1][z2+1]++; } S.x=read,S.y=read,S.z=read; T.x=read,T.y=read,T.z=read; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++){ b[i][j][k]=a[i][j][k]+b[i-1][j][k]+ b[i][j-1][k]+b[i][j][k-1]-b[i-1][j-1][k] -b[i-1][j][k-1]-b[i][j-1][k-1]+b[i-1][j-1][k-1]; } cout<<bfs()<<endl; } return 0; } /* */
