首页 > 代码库 > hdu 1253 胜利大逃亡(bfs)

hdu 1253 胜利大逃亡(bfs)

胜利大逃亡

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 20468    Accepted Submission(s): 8152
题意给出一个长宽高为A,B,C,三维的地图要求在规定时间内从(0,0,0,)走到(A-1,B-1,C-1
三维bfs  模板题不多讲注意对应好坐标就行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
int d[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
int n,m,h,T;
int map[55][55][55];
int vis[55][55][55];
struct node{
    int x,y,z;
    int depth;//记录所用时间
};

bool jud(int x,int y,int z)
{

    if(x<0||x>=h||y<0||y>=n||z<0||z>=m)
        return false;
    if(vis[x][y][z])
        return false;
    if(map[x][y][z]==1)
        return false;
    return true;

}
int bfs(int t,int x,int y)
{
    int i,j,k;
    queue<node> q;
    node a,b,c;
    a.z=t;
    a.x=x;
    a.y=y;
    a.depth=0;
    q.push(a);
    vis[0][0][0]=1;
    while(!q.empty())
    {

        b=q.front();
        q.pop();
        if(b.z==h-1&&b.x==n-1&&b.y==m-1)
            return b.depth;
        for(i=0;i<6;i++)
        {
            c.x=b.x+d[i][0];
            c.y=b.y+d[i][1];
            c.z=b.z+d[i][2];
            if(!jud(c.z,c.x,c.y))
                continue;
                vis[c.z][c.x][c.y]=1;
                c.depth=b.depth+1;
                if(c.z==h-1&&c.x==n-1&&c.y==m-1)
                    return c.depth;
                    q.push(c);
        }
    }
    return -1;

}
int main()
{
    int cas,i,j,k,ans;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d%d%d",&h,&n,&m,&T);
        memset(vis,0,sizeof(vis));
        for(i=0;i<h;i++)
         for(j=0;j<n;j++)
         for(k=0;k<m;k++)
         {
             scanf("%d",&map[i][j][k]);
         }
          if(map[h-1][n-1][m-1]==1 ||h+n+m-3>T)
        {
            printf("-1\n");
            continue;
        }
         ans=bfs(0,0,0);
         if(ans<=T)
            printf("%d\n",ans);
            else
                printf("-1\n");

    }
    return 0;
}


hdu 1253 胜利大逃亡(bfs)