hdu1253 参考答案

   1 /*
   2 hdu 1253 经典：三维BFS＋剪枝
   3 ymc 2008/09/18
   4 题目大意：
   5 三维地图A×B×C，0代表路，1代表0。人在S(0,0,0),出口在E(A-1,B-1,C-1)。
   6 求人能否在T时间能达到出口，以及最短时间。
   7 分析与解题思路：
   8 经典的BFS，但是不剪枝会TLE。
   9 剪枝方法：每次搜索到一个新的点P1(x1,y1,z1)的时候，设S到P1的距离
  10 为SP1，P1到E的估计最短距离为P1E。若SP1＋P1E>T,剪枝。
  11 */
  12 #include <iostream>
  13 #include <queue>
  14 using namespace std;
  15 const int N=55;
  16 int map[N][N][N];
  17 int dist[N][N][N];
  18 int A,B,C,T;
  19 int step[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}};
  20 void BFS()
  21 {
  22     memset(dist,-1,sizeof(dist));
  23     dist[0][0][0]=0;
  24     queue<int> q;
  25     q.push(0);q.push(0);q.push(0);
  26     int x,y,z,x1,y1,z1;
  27     int tmp;
  28     while(!q.empty())
  29     {
  30         x=q.front();q.pop();
  31         y=q.front();q.pop();
  32         z=q.front();q.pop();
  33         if(x==A-1&&y==B-1&&z==C-1)
  34             return;
  35         if(dist[x][y][z]>T)//剪枝
  36             return;
  37         for(int k=0;k<6;k++)
  38         {
  39             x1=x+step[k][0];
  40             y1=y+step[k][1];
  41             z1=z+step[k][2];
  42             if(x1<0||x1>=A||y1<0||y1>=B||z1<0||z1>=C)
  43                 continue;
  44             if(map[x1][y1][z1]==1||dist[x1][y1][z1]>=0)
  45                 continue;
  46             dist[x1][y1][z1]=dist[x][y][z]+1;
  47             tmp=A+B+C-x1-y1-z1-3;
  48             if(tmp+dist[x1][y1][z1]<=T)//剪枝，重要，不然TLE
  49             {
  50                 q.push(x1),q.push(y1),q.push(z1);
  51             }
  52         }
  53     }
  54 }
  55 int main()
  56 {
  57     int test;
  58     scanf("%d",&test);
  59     while(test-->0)
  60     {
  61         scanf("%d %d %d %d",&A,&B,&C,&T);
  62         for(int i=0;i<A;i++)
  63             for(int j=0;j<B;j++)
  64                 for(int k=0;k<C;k++)
  65                     scanf("%d",&map[i][j][k]);
  66         BFS();
  67         if(dist[A-1][B-1][C-1]>T||dist[A-1][B-1][C-1]==-1)//可能会是T+1
  68             printf("-1\n");
  69         else
  70             printf("%d\n",dist[A-1][B-1][C-1]);
  71     }
  72 }