https://www.acwing.com/problem/content/4711/
题目没什么难度,但是就是三维有些东西不经常定义记不住。写个题解记录一下吧
Acwing 1096.地牢大师
https://www.acwing.com/problem/content/1098/
同为三维bfs
三维方向定义(6个方位)
LL dx[]={-1,0,0,0,0,1};
LL dy[]={0,0,0,1,-1,0};
LL dz[]={0,1,-1,0,0,0};
三维长宽高存储
struct Point
{
LL x;
LL y;
LL z;
};//(一定要记得这个分号!不然会报错)
queue存储调用
queue<Point> que;
完整代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL N=200200,M=100;
LL k,n,m,l,r;
LL dist[M][M][M];
char a[M][M][M];
LL dx[]={-1,0,0,0,0,1};
LL dy[]={0,0,0,1,-1,0};
LL dz[]={0,1,-1,0,0,0};
struct Point
{
LL x;
LL y;
LL z;
};
LL bfs(LL o,LL p,LL q)
{
memset(dist,-1,sizeof dist);
dist[o][p][q]=0;
queue<Point> que;
que.push({o,p,q});
while(que.size())
{
auto t=que.front();
que.pop();
for(LL i=0;i<6;i++)
{
LL xx=dx[i]+t.x,yy=dy[i]+t.y,zz=dz[i]+t.z;
if(xx>=1&&xx<=k&&yy>=1&&yy<=n&&zz>=1&&zz<=m&&dist[xx][yy][zz]==-1&&a[xx][yy][zz]!='#')
{
dist[xx][yy][zz]=dist[t.x][t.y][t.z]+1;
que.push({xx,yy,zz});
}
}
}
return dist[k][n][m];
}
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int T=1;
//cin>>T;
while(T--)
{
cin>>k>>n>>m;//k层,每一层都是n*m
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
for(int q=1;q<=m;q++)
{
cin>>a[i][j][q];
}
}
}
cin>>l>>r;
bfs(1,l,r);
LL ans=0;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=n;j++)
{
for(int q=1;q<=m;q++)
{
if(dist[i][j][q]>=0) ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}
标签:dist,LL,三维,4708,bfs,que,&&,Acwing
From: https://www.cnblogs.com/Vivian-0918/p/16833677.html