ACM 532 Dungeon Master
BFS的第2次 >< 好HIGH
這題有6個方向走,跟NPSC的喵喵抓老鼠很像
/************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char x[33];
main()
{
int n,m,l,r,a,b,c,ii,jj;
while(scanf("%d %d %d",&l,&r,&n)==3&&l!=0)
{
int map[33][33][33]={0},g;
for(c=0;c<=l+1;c++)
for(a=0;a<=r+1;a++)
for(b=0;b<=n+1;b++)
map[c][a][b]=-1;
for(c=1;c<=l;c++) /*樓層*/
for(a=1;a<=r;a++)
{
scanf("%s",x);
m=strlen(x);
for(b=0;b<m;b++)
{
if(x[b]=='#') map[c][a][b+1]=-1;
else if(x[b]=='E') map[c][a][b+1]=-2;
else if(x[b]=='S') {ii=a;jj=b+1;g=c;map[c][a][b+1]=0;}
else map[c][a][b+1]=0;
}
}
/*圖形牆壁為-1 E為-2 起始點不採用標記 原因:複雜化了*/
int stack[27001][3]={0},top=0;
int ans=0;
stack[0][0]=ii;stack[0][1]=jj;stack[0][2]=g;
for(a=0;a<=top;a++)
{
int nn=stack[a][0],mm=stack[a][1],gg=stack[a][2];
if(map[gg][nn-1][mm]==-2||map[gg][nn][mm-1]==-2||map[gg][nn+1][mm]==-2||map[gg][nn][mm+1]==-2||map[gg+1][nn][mm]==-2||map[gg-1][nn][mm]==-2) {ans=map[gg][nn][mm]+1;break;}
if(map[gg][nn-1][mm]==0)
{
map[gg][nn-1][mm]=map[gg][nn][mm]+1;
top++;
stack[top][0]=nn-1;stack[top][1]=mm;stack[top][2]=gg;
}
if(map[gg][nn][mm-1]==0)
{
map[gg][nn][mm-1]=map[gg][nn][mm]+1;
top++;
stack[top][0]=nn;stack[top][1]=mm-1;stack[top][2]=gg;
}
if(map[gg][nn+1][mm]==0)
{
map[gg][nn+1][mm]=map[gg][nn][mm]+1;
top++;
stack[top][0]=nn+1;stack[top][1]=mm;stack[top][2]=gg;
}
if(map[gg][nn][mm+1]==0)
{
map[gg][nn][mm+1]=map[gg][nn][mm]+1;
top++;
stack[top][0]=nn;stack[top][1]=mm+1;stack[top][2]=gg;
}
if(map[gg+1][nn][mm]==0)
{
map[gg+1][nn][mm]=map[gg][nn][mm]+1;
top++;
stack[top][0]=nn;stack[top][1]=mm;stack[top][2]=gg+1;
}
if(map[gg-1][nn][mm]==0)
{
map[gg-1][nn][mm]=map[gg][nn][mm]+1;
top++;
stack[top][0]=nn;stack[top][1]=mm;stack[top][2]=gg-1;
}
}
if(ans==0) printf("Trapped!\n");
else printf("Escaped in %d minute(s).\n",ans);
}
return 0;
}