hdu1253 参考答案

返回“大学生程序设计竞赛”

/*
hdu 1253 经典：三维BFS＋剪枝
ymc 2008/09/18
题目大意：
三维地图A×B×C，0代表路，1代表0。人在S(0,0,0),出口在E(A-1,B-1,C-1)。
求人能否在T时间能达到出口，以及最短时间。
分析与解题思路：
经典的BFS，但是不剪枝会TLE。
剪枝方法：每次搜索到一个新的点P1(x1,y1,z1)的时候，设S到P1的距离
为SP1，P1到E的估计最短距离为P1E。若SP1＋P1E>T,剪枝。
*/
#include <iostream>
#include <queue>
using namespace std;
const int N=55;
int map[N][N][N];
int dist[N][N][N];
int A,B,C,T;
int step[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
void BFS()
{
    memset(dist,-1,sizeof(dist));
    dist[0][0][0]=0;
    queue<int> q;
    q.push(0);q.push(0);q.push(0);
    int x,y,z,x1,y1,z1;
    int tmp;
    while(!q.empty())
    {
        x=q.front();q.pop();
        y=q.front();q.pop();
        z=q.front();q.pop();
        if(x==A-1&&y==B-1&&z==C-1)
            return;
        if(dist[x][y][z]>T)//剪枝
            return;
        for(int k=0;k<6;k++)
        {
            x1=x+step[k][0];
            y1=y+step[k][1];
            z1=z+step[k][2];
            if(x1<0||x1>=A||y1<0||y1>=B||z1<0||z1>=C)
                continue;
            if(map[x1][y1][z1]==1||dist[x1][y1][z1]>=0)
                continue;
            dist[x1][y1][z1]=dist[x][y][z]+1;
            tmp=A+B+C-x1-y1-z1-3;
            if(tmp+dist[x1][y1][z1]<=T)//剪枝，重要，不然TLE
            {
                q.push(x1),q.push(y1),q.push(z1);
            }
        }
    }
}
int main()
{
    int test;
    scanf("%d",&test);
    while(test-->0)
    {
        scanf("%d %d %d %d",&A,&B,&C,&T);
        for(int i=0;i<A;i++)
            for(int j=0;j<B;j++)
                for(int k=0;k<C;k++)
                    scanf("%d",&map[i][j][k]);
        BFS();
        if(dist[A-1][B-1][C-1]>T||dist[A-1][B-1][C-1]==-1)//可能会是T+1
            printf("-1\n");
        else
            printf("%d\n",dist[A-1][B-1][C-1]);
    }
}