HDU 1253 - 胜利大逃亡
Problem: a* b* c 立方体,从(1,1,1)到(a,b,c),最短路<=限制时间
Solution: BFS
Code:
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
inline ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
int t,a,b,c,ti,ans;
int mp[55][55][55];
int vis[55][55][55];
int dx[6]={-1,1,0,0,0,0};
int dy[6]={0,0,-1,1,0,0};
int dz[6]={0,0,0,0,-1,1};
struct node{
int x,y,z,cnt;
};
int solve(int x,int y,int z){
node p={x,y,z,0};
queue<node>q;
q.push(p);
vis[x][y][z]=1;
while(!q.empty()){
node t=q.front();
q.pop();
if(t.x==a&&t.y==b&&t.z==c&&t.cnt<=ti) return t.cnt;
for(int i=0;i<6;i++){
int xx=t.x+dx[i],yy=t.y+dy[i],zz=t.z+dz[i];
if(xx<1||xx>a||yy<1||yy>b||zz<1||zz>c||vis[xx][yy][zz]||mp[xx][yy][zz]) continue;
vis[xx][yy][zz]=1;
q.push({xx,yy,zz,t.cnt+1});
}
}
return -1;
}
int main() {
t=read();
while(t--){
a=read(),b=read(),c=read(),ti=read();
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
for(int k=1;k<=c;k++){
mp[i][j][k]=read();
}
}
}
memset(vis,0,sizeof(vis));
ans=solve(1,1,1);
printf("%d\n",ans);
}
return 0;
}