题目地址：http://ac.jobdu.com/problem.php?cid=1040&pid=85
无费地址：http://acmclub.com/problem.php?id=1209
//九度OJ 教程86广度优先搜索迷宫之《胜利大逃亡》//http://ac.jobdu.com/problem.php?cid=1040&pid=85#include<stdio.h>#include<string.h>#define MAXS 53#include<queue>using namespace std;typedef struct E{ int a; int b; int c;}E;//记录坐标的结构体queue<E> Q;int main(){ int mark[MAXS][MAXS][MAXS]; int k,a,b,c,t,flag,ia,ib,ic,tt,count; E loc,temp,temp2; memset(mark,1,MAXS*MAXS*MAXS*sizeof(int)); scanf("%d",&k); while(k--) { loc.a=loc.b=loc.c=flag=1;//暂时flag设为成功。无视题意，借鉴哨兵想法，把（1,1,1）当做入口，(a,b,c)当做出口 while(Q.empty()==false)Q.pop(); scanf("%d %d %d %d",&a,&b,&c,&t); for(ia=1;ia<=a;ia++) for(ib=1;ib<=b;ib++) for(ic=1;ic<=c;ic++) scanf("%d",&mark[ia][ib][ic]); if(mark[1][1][1]||mark[a][b][c])//入口或者出口已经被墙堵死了 { printf("-1\n"); continue; } Q.push(loc);//(1,1,1)这个坐标点进队…… mark[1][1][1]=1;//设置访问标记。 for(tt=0;tt<t&&flag&&(mark[a][b][c]==0);tt++)//广度优先遍历该图。边界条件设定：如果a=b=c=1时，tt为0时完成下列循环，并且标记mark[a][b][c]为1。tt++变成1后推出循环（而此时其实花费的实际时间为0）。故，最后时间得 { count=Q.size(); while(count--) { temp=Q.front(); Q.pop(); mark[temp.a][temp.b][temp.c]=1;//标记已经访问了。 if(mark[temp.a-1][temp.b][temp.c]==0) { temp2=temp; temp2.a--; Q.push(temp2); mark[temp.a-1][temp.b][temp.c]=1; } if(mark[temp.a+1][temp.b][temp.c]==0) { temp2=temp; temp2.a++; Q.push(temp2); mark[temp.a+1][temp.b][temp.c]=1; } if(mark[temp.a][temp.b+1][temp.c]==0) { temp2=temp; temp2.b++; Q.push(temp2); mark[temp.a][temp.b+1][temp.c]=1; } if(mark[temp.a][temp.b-1][temp.c]==0) { temp2=temp; temp2.b--; Q.push(temp2); mark[temp.a][temp.b-1][temp.c]=1; } if(mark[temp.a][temp.b][temp.c+1]==0) { temp2=temp; temp2.c++; Q.push(temp2); mark[temp.a][temp.b][temp.c+1]=1; } if(mark[temp.a][temp.b][temp.c-1]==0) { temp2=temp; temp2.c--; Q.push(temp2); mark[temp.a][temp.b][temp.c-1]=1; } }//while if(Q.empty()==true)flag=0;//全部被墙堵死了 }//for if(mark[a][b][c])//直到循环结束，如果mark[a][b][c]已被标记，不管咋样都算是成功逃脱了。 printf("%d\n",tt); else printf("-1\n");//到最后，出口的房间还是没被标记，就是还没逃脱。 }//while return 0;}