九度OJ 教程86 广度优先搜索解决迷宫问题之《胜利大逃亡》

题目地址：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;}}//whileif(Q.empty()==true)flag=0;//全部被墙堵死了}//forif(mark[a][b][c])//直到循环结束，如果mark[a][b][c]已被标记，不管咋样都算是成功逃脱了。printf("%d\n",tt);else printf("-1\n");//到最后，出口的房间还是没被标记，就是还没逃脱。}//whilereturn 0;}