链接:

时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 131072K,其他语言262144K
64bit IO Format:%lld

题目描述

Nancy喜欢吃果冻! Nancy钻进了一个n \times n \times
nn×n×n的果冻里,她想从(1,1,1)一路上、下、左、右、前、后六个方向吃到(n,n,n)。
但果冻毕竟是有许多口味的,标记为*的口味是Nancy不愿意吃的,其余的果冻均标记为.。 Nancy不想吃坏肚子,于是她想尽可能少的吃果冻。
下面给出果冻的情况,请你帮忙计算一下她能吃多少块果冻叭!

输入描述:

第一行:一个整数n。 接下来n层,每组n行,每行n列,表示果冻(i,j,k)的情况(如题目描述所述)。

数据满足:1≤n≤100,保证果冻(1,1,1)不是Nancy不愿意吃的。
输出描述:
如果可以到达(n,n,n),请输出路上吃的果冻数量,否则请输出-1。
示例1
输入

2
.*
..
*.
..

输出

4

题解:
三维版dfs
方向向量:
int dx[]={0,1,0,-1,0,0};
int dy[]={1,0,-1,0,0,0};
int dz[]={0,0,0,0,1,-1};
dis用于记录步数
for循环枚举方向向量,从(1,1,1)开始分别向上、下、左、右、前、后六个方向探索,如果不是 * 就加一
最后输出dis[n][n][n]
代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=104;
char a[maxn][maxn][maxn];

int dx[]={
   0,1,0,-1,0,0};
int dy[]={
   1,0,-1,0,0,0};
int dz[]={
   0,0,0,0,1,-1};
struct edge{
   
	int x,y,z;
};
queue<edge>q;
int dis[maxn][maxn][maxn];

int main()
{
   
	int n;
	cin>>n;
	char ch=getchar();
	for(int i=1;i<=n;i++)
	{
   
			for(int j=1;j<=n;j++)
		{
   
			for(int k=1;k<=n;k++)
			{
   
				cin>>a[i][j][k];
			}
			ch=getchar(); 
		}
	}
	if(a[n][n][n]=='*')
	{
   
		cout<<-1;
		return 0;
	}
	q.push((edge){
   1,1,1});
	dis[1][1][1]=1;
	while(!q.empty())
	{
   
		edge now=q.front();
		q.pop();
		int x,y,z;
		for(int i=0;i<6;i++)
		{
   
			x=now.x+dx[i];
			y=now.y+dy[i];
			z=now.z+dz[i];
			if(x&&y&&z&&x<=n&&y<=n&&z<=n&&a[x][y][z]!='*'&&dis[x][y][z]==0)
			{
   
				dis[x][y][z]=dis[now.x][now.y][now.z]+1;
				q.push((edge){
   x,y,z});
			}
		}
	}
	cout<<dis[n][n][n];

}