hdu1072 参考答案

   1 /*
   2 hdu 1072  经典：最短路径问题Floyd＋SPFA
   3 ymc 2008/09/17
   4 题目大意：
   5 在n×m的地图上，0表示墙，1表示空地，2表示人
   6 3表示目的地，4表示有炸弹重启器。
   7 炸弹的时间是6，人走一步所需要的时间是1。
   8 每次可以上、下、左、右移动一格。当人走到4时
   9 如果炸弹的时间不是0，可以重新设定炸弹的时间为6。
  10 如果人走到3而炸弹的时间不为0时，成功走出。
  11 求人从2走到3的最短时间。
  12 分析与解题思路：
  13 1.首先用Floyd求出所有可行走的点之间的最短距离。
  14 2.然后得到所有2，3，4之间的最短距离，如果整个距离超过5
  15 则设置为Max。
  16 3.用SPFA求2到3的最短距离。
  17 */
  18 #include <iostream>
  19 #include <queue>
  20 using namespace std;
  21 const int N=10;
  22 const int M=N*N;
  23 const int Max=(1<<24)+(1<<16)+(1<<8)+1;
  24 int map[N][N];
  25 int n,m;
  26 int dist[M][M];
  27 int ans[M*M];
  28 bool inqueue[M*M];
  29 int num;
  30 int s,t;
  31 int step[2][2]={{1,0},{0,1}};//只需要两个方向
  32 void Init()
  33 {
  34     scanf("%d %d",&n,&m);
  35     for(int i=0;i<n;i++)
  36         for(int j=0;j<m;j++)
  37         {
  38             scanf("%d",&map[i][j]);
  39             if(map[i][j]==2)//起点，
  40             {
  41                 s=i*m+j;
  42                 map[i][j]=4;
  43             }
  44             else if(map[i][j]==3)//终点
  45             {
  46                 t=i*m+j;
  47                 map[i][j]=4;
  48             }
  49         }
  50     memset(dist,1,sizeof(dist));
  51     num=n*m;
  52     int x,y;
  53     int i1,j1;
  54     for(int i=0;i<n;i++)//相邻的两点是否能走
  55         for(int j=0;j<m;j++)
  56         {
  57             if(map[i][j]==0)
  58                 continue;
  59             x=i*m+j;
  60             for(int k=0;k<2;k++)
  61             {
  62                 i1=i+step[k][0];
  63                 j1=j+step[k][1];
  64 
  65                 if(i1<0||i1>=n||j1<0||j1>=m||map[i1][j1]==0)
  66                     continue;
  67                 y=i1*m+j1;
  68                 dist[x][y]=1;
  69                 dist[y][x]=1;
  70             }
  71         }
  72 }
  73 void Floyd()
  74 {
  75     for(int k=0;k<num;k++)
  76         for(int i=0;i<num;i++)
  77             for(int j=0;j<num;j++)
  78                 if(dist[i][j]>dist[i][k]+dist[k][j])
  79                     dist[i][j]=dist[i][k]+dist[k][j];
  80 }
  81 void SPFA()
  82 {
  83     memset(ans,1,sizeof(ans));
  84     memset(inqueue,0,sizeof(inqueue));
  85     queue<int> q;
  86     q.push(s);
  87     ans[s]=0;
  88     inqueue[s]=true;
  89     int u;
  90     while(!q.empty())
  91     {
  92         u=q.front();q.pop();
  93         for(int v=0;v<num;v++)
  94         {
  95             if(dist[u][v]==Max)
  96                 continue;
  97             if(ans[v]>ans[u]+dist[u][v])
  98             {
  99                 ans[v]=ans[u]+dist[u][v];
 100                 if(!inqueue[v])
 101                 {
 102                     inqueue[v]=true;
 103                     q.push(v);
 104                 }
 105             }
 106         }
 107         inqueue[u]=true;
 108     }
 109 }
 110 void Solve()
 111 {
 112     Floyd();
 113     int x,y,x1,y1;
 114     for(int i=0;i<num;i++)
 115     {
 116         x=i/m;
 117         y=i%m;
 118         for(int j=0;j<num;j++)
 119         {
 120             x1=j/m;
 121             y1=j%m;
 122             if(map[x][y]!=4||map[x1][y1]!=4||dist[i][j]>5)//2，3,4之间距离小于6
 123                 dist[i][j]=Max;
 124         }
 125     }
 126     SPFA();
 127 }
 128 int main()
 129 {
 130     int test;
 131     scanf("%d",&test);
 132     while(test-->0)
 133     {
 134         Init();
 135         Solve();
 136         if(ans[t]==Max)
 137             printf("-1\n");
 138         else
 139             printf("%d\n",ans[t]);
 140     }
 141 }