题目链接:
http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?cid=11691&pid=1005&ojid=0
解析:
本题就是一个三维的迷宫，只要把方向改成6个(上，下，左，右，前，后)，再套BFS模板
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; #define MAXN 60 #define inf 999999999 typedef struct local { int z; //表示第三维坐标 int x,y; int time; }loca; int direction[6][3]={{1,0,0},{0,1,0},{-1,0,0},{0,-1,0},{0,0,1},{0,0,-1}}; typedef struct Graph { int graph[MAXN][MAXN]; }gra; gra map[MAXN]; gra visit[MAXN]; int n,m,s,ans,A,T; int check(int x,int y,int z) { if(visit[z].graph[x][y]==0&&x>=1&&x<=n&&y>=1&&y<=m&&z>=1&&z<=A&&map[z].graph[x][y]==0) { return 1; } return 0; } void BFS(loca start) { queue<loca>step; int i; loca tmp; visit[start.z].graph[start.x][start.y]=1; step.push(start); while(step.size()) { tmp=step.front(); if(tmp.z==A&&tmp.x==n&&tmp.y==m&&tmp.time<=T) { ans=tmp.time; break; } if(tmp.time>T)break; step.pop(); loca oth; int x,y,z; for(i=0;i<6;i++) { x=tmp.x+direction[i][0]; y=tmp.y+direction[i][1]; z=tmp.z+direction[i][2]; if(check(x,y,z)) { oth.time=tmp.time+1; oth.x=x; oth.y=y; oth.z=z; step.push(oth); visit[z].graph[x][y]=1; } } } } int main() { int i,j,s1,s2,t,k; loca start; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&A,&n,&m,&T); memset(visit,0,sizeof(visit)); for(i=1;i<=A;i++) { for(j=1;j<=n;j++) { for(k=1;k<=m;k++) { scanf("%d",&map[i].graph[j][k]); } } } ans=inf; start.x=1; start.y=1; start.z=1; start.time=0; BFS(start); if(ans==inf) printf("-1\n"); else printf("%d\n",ans); } return 0; }