bfs水题。
变成3维而已。定义3维变量就好.
int xx[]={0,0,0,0,⑴,1};
int yy[]={0,0,⑴,1,0,0};
int zz[]={⑴,1,0,0,0,0};
这样就和平时做的简单宽搜没甚么区分了。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<vector>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e⑻
#define LL long long
#define PI 3.141592654
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,n) for(int i= a;i< n ;i++)
#define FOR0(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
#define acfun std::ios::sync_with_stdio(false)
#define SIZE 50+1
using namespace std;
int xx[]={0,0,0,0,⑴,1};
int yy[]={0,0,⑴,1,0,0};
int zz[]={⑴,1,0,0,0,0};
struct lx
{
int x,y,z;
int t;
void init(int xx,int yy,int zz,int tt)
{
x=xx,y=yy,z=zz,t=tt;
}
};
int a,b,c,t;
bool g[SIZE][SIZE][SIZE];
void bfs()
{
bool vis[SIZE][SIZE][SIZE];
CLR(vis,0);
vis[0][0][0]=1;
lx tmp;
tmp.init(0,0,0,0);
queue<lx>q;
q.push(tmp);
while(!q.empty())
{
tmp=q.front();
q.pop();
//printf("%d %d %d
",tmp.x,tmp.y,tmp.z);
if(tmp.x==a⑴&&tmp.y==b⑴&&tmp.z==c⑴&&tmp.t<=t)
{
printf("%d
",tmp.t);
return;
}
FOR(k,0,6)
{
int x=tmp.x+xx[k];
int y=tmp.y+yy[k];
int z=tmp.z+zz[k];
if(x<0||y<0||z<0||x>=a||y>=b||z>=c||g[x][y][z]||vis[x][y][z])continue;
vis[x][y][z]=1;
lx now;
now.init(x,y,z,tmp.t+1);
q.push(now);
}
}
puts("⑴");
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&a,&b,&c,&t);
FOR(i,0,a)
FOR(j,0,b)
FOR(k,0,c)
scanf("%d",&g[i][j][k]);
bfs();
}
}