学步园

这个题只需建一个3维数组即可。其余与普通广搜一样。

#include <stdio.h>
void Init();
int BFS();
int a[30][30][30],c[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};
int L,R,C,x0,y0,z0,x1,y1,z1;
void Init()
{
    int i,j,k;
    char chr;
    for (i=0;i<L;getchar(),i++)
        for (j=0;j<R;j++)
		{ 
			getchar();
			for (k=0;k<C;k++)
            {
                chr=getchar();
                if (chr=='#') a[i][j][k]=-1;
                else if (chr=='.') a[i][j][k]=0;
                    else if (chr=='S'){x0=i;y0=j;z0=k;a[i][j][k]=0;}
                        else{x1=i;y1=j;z1=k;a[i][j][k]=0;}
            }
		}
}
int BFS()
{
    int b[27000][3];
    int i,j,t0,t1,t2,t3,x,y,z;
    b[0][0]=x0;
    b[0][1]=y0;
    b[0][2]=z0;
    t1=0;
    t0=t2=t3=1;
    for (;t1<t2;t1=t2,t2=t3,t0++)//t0存步数，t1,t2记录一步的开始和结束在b数组中存的位置。
        for (i=t1;i<t2;i++)
        {
            for (j=0;j<6;j++)
            {
                x=b[i][0]+c[j][0];
                y=b[i][1]+c[j][1];
                z=b[i][2]+c[j][2];
                if (x>=0&&y>=0&&z>=0&&x<L&&y<R&&z<C&&a[x][y][z]==0)
                {
                    b[t3][0]=x;
                    b[t3][1]=y;
                    b[t3][2]=z;
                    a[x][y][z]=t0;
                    t3++;
                }
            }
            if (a[x1][y1][z1]>0) return t0;
        }
    return 0;
}
int main()
{
    int s;
    scanf("%d%d%d",&L,&R,&C);
    while (L>0)
    {
        Init();
        s=BFS();
        if (s>0) printf("Escaped in %d minute(s).\n",s);
        else printf("Trapped!\n");
        scanf("%d%d%d",&L,&R,&C);
    }
    return 0;
}