hdoj1253——三维bfs

http://acm.hdu.edu.cn/showproblem.php?pid=1253

思路很简单,就是增加了一维搜索维度,读入maze[][][]时特别要特别注意下标和自己建的坐标系对应(在这调试了很久broken heart。。)900多MS

 

 

#include<stdio.h>
#include<stdlib.h>
typedef struct Queue{
    int x,y,z;
    int depth;
}Queue;
Queue queue[125010];
int iq=0;
int x[7],y[7],z[7];
int main()
{
    int cas;
    x[1]=0;y[1]=-1;z[1]=0;
    x[2]=0;y[2]=1;z[2]=0;
    x[3]=-1;y[3]=0;z[3]=0;
    x[4]=1;y[4]=0;z[4]=0;
    x[5]=0;y[5]=0;z[5]=-1;
    x[6]=0;y[6]=0;z[6]=1;
    scanf("%d",&cas);
    while(cas--)
    {
        int maze[52][52][52],a,b,c,t,i,j,k;
        bool visit[52][52][52];
        iq=0;
        scanf("%d %d %d %d",&a,&b,&c,&t);
        for(i=0;i<=a+1;i++)
            for(j=0;j<=b+1;j++)
                for(k=0;k<=c+1;k++)
                {
                    visit[k][j][i]=true;
                }
        for(i=1;i<=a;i++)
            for(j=1;j<=b;j++)
                for(k=1;k<=c;k++)
                {
                    scanf("%d",&maze[k][j][i]);
                    if(maze[k][j][i]==0)
                        visit[k][j][i]=false;
                }
        Queue temp;
        temp.x=1;
        temp.y=1;
        temp.z=1;
        temp.depth=0;
        queue[iq++]=temp;
        visit[1][1][1]=true;
        bool flag=false;
        for(i=0;i<=iq-1;i++)
        {
            int curx=queue[i].x;
            int cury=queue[i].y;
            int curz=queue[i].z;
            for(j=1;j<=6;j++)
            {
                if(!visit[curx+x[j]][cury+y[j]][curz+z[j]] && !flag)
                {
                    visit[curx+x[j]][cury+y[j]][curz+z[j]]=true;
                    temp.x=curx+x[j];
                    temp.y=cury+y[j];
                    temp.z=curz+z[j];
                    temp.depth=queue[i].depth+1;
                    queue[iq++]=temp;
                    if(temp.depth>t)
                        break;
                    if(temp.x==c && temp.y==b && temp.z==a)
                    {
                        flag=true;
                        break;
                    }
                }

            }
            if(temp.depth>t || flag)
                break;
        }
        if(flag)
            printf("%d\n",queue[iq-1].depth);
        else
            printf("-1\n");
    }
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>