2019CCPC厦门站 H. Zayin and Obstacles（三维前缀和 bfs）

2019CCPC厦门站 H. Zayin and Obstacles（三维前缀和 bfs）

题意：

思路：

代码：

#includeusing namespace std;typedef long long ll;typedef unsigned long long ull;typedef pairPLL;typedef pairPII;typedef pairPDD;#define I_int llinline 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); queueq; 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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。