链接:https://ac.nowcoder.com/acm/problem/201613 来源:牛客网
Nancy喜欢吃果冻!
Nancy钻进了一个n×n×nn \times n \times nn×n×n的果冻里,她想从(1,1,1)一路上、下、左、右、前、后六个方向吃到(n,n,n)。
但果冻毕竟是有许多口味的,标记为*的口味是Nancy不愿意吃的,其余的果冻均标记为.。
Nancy不想吃坏肚子,于是她想尽可能少的吃果冻。 下面给出果冻的情况,请你帮忙计算一下她能吃多少块果冻叭!
做法:误打误撞写了个三维bfs模板题,也是调了有一会,感觉大佬的题解有点难懂,在结构体装一个当前状态的步数感觉更通俗易懂,然后就是处理步数问题,如果下一步是终点的话,就直接输出cnt+1就行,不行就是-1.(这里记得先初始化为-1)!!!注意在剪掉情况的时候一定要记得把如果此情况被赋值过就跳过加上,要不然会MLE
//本题代码
#include<bits/stdc++.h>
#define endl "\n"
#define ll long long
//dont forget to check long long
struct node{
int x,y,z;
int num;
};
int n,m;
char s[110][110][110];
std::queue<node> q;
int d[6][3]={{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,1},{0,0,-1}};
int vis[110][110][110];
void bfs()
{
node t;
t.x=1,t.y=1,t.z=1,t.num=1;
q.push(t);
vis[1][1][1]=1;
while(!q.empty())
{
auto pos=q.front();
q.pop();
int x=pos.x,y=pos.y,z=pos.z;
int cnt=pos.num;
for(int i=0;i<6;i++)
{
int dx=x+d[i][0];
int dy=y+d[i][1];
int dz=z+d[i][2];
if(dx<1||dy<1||dz<1||dx>n||dy>n||dz>n||s[dx][dy][dz]=='*'||vis[dx][dy][dz]!=-1) continue;
if(vis[dx][dy][dz]==-1)
{
vis[dx][dy][dz]=cnt+1;
}
if(dx==n&&dy==n&&dz==n)
{
std::cout<<cnt+1<<endl;
return ;
}
q.push((node){dx,dy,dz,cnt+1});
}
}
std::cout<<-1<<endl;
}
void slove()
{
//int n;
std::cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
std::cin>>s[i][j][k];
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
vis[i][j][k]=-1;
}
}
}
bfs();
//std::cout<<vis[n][n][n]<<endl;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int T=1;
//std::cin>>T;
while(T--)
{
slove();
}
return 0;
}