题目描述
Ignatius被魔王抓走了,有一天魔王出差去了,这可是Ignatius逃亡的好机会.
魔王住在一个城堡里,城堡是一个ABC的立方体,可以被表示成A个B*C的矩阵,刚开始Ignatius被关在(0,0,0)的位置,离开城堡的门在(A-1,B-1,C-1)的位置,现在知道魔王将在T分钟后回到城堡,Ignatius每分钟能从一个坐标走到相邻的六个坐标中的其中一个.现在给你城堡的地图,请你计算出Ignatius能否在魔王回来前离开城堡(只要走到出口就算离开城堡,如果走到出口的时候魔王刚好回来也算逃亡成功),如果可以请输出需要多少分钟才能离开,如果不能则输出-1.
分析
一个三维的bfs,只有当前坐标上的点为0时才可以行动,最后要看时间是否小于魔王回来的时间T。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
int T,n,m,p,K,ans;
int dx[6]={0,1,0,-1,0,0},dy[6]={1,0,-1,0,0,0},dz[6]={0,0,0,0,1,-1};
bool st[50][50][50];
int g[50][50][50];
struct point{
int z,x,y,time;
};
bool bfs()
{
memset(st,0,sizeof st);
point start;
start.z=start.y=start.x=start.time=0;
st[0][0][0]=true;
queue<point> q;
q.push(start);
while(q.size())
{
auto t=q.front();
q.pop();
if(t.x==n-1 && t.y==m-1 && t.z==p-1)
{
ans=t.time;
return true;
}
point cur;
for(int i=0;i<6;i++)
{
cur.x=t.x+dx[i];
cur.y=t.y+dy[i];
cur.z=t.z+dz[i];
cur.time=t.time+1;
if(cur.time>T)
continue;
if(cur.x>=0 && cur.x<n && cur.y>=0 && cur.y<m && cur.z>=0 && cur.z<p && g[cur.z][cur.x][cur.y]==0 && !st[cur.z][cur.x][cur.y])
{
st[cur.z][cur.x][cur.y]=true;
q.push(cur);
}
}
}
return false;
}
int main()
{
scanf("%d",&K);
while(K--)
{
ans=0;
scanf("%d%d%d%d",&p,&n,&m,&T);
for(int k=0;k<p;k++)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
scanf("%d",&g[k][i][j]);
}
}
}
if(bfs()) printf("%d\n",ans);
else puts("-1");
}
return 0;
}