poj3026Borg Maze（bfs+MST)

BFS求出任意两个A或A和S的最短距离然后最小生成树求和
把所有A和S存起来求BFS任意两点搜超时了之后改了改过了
View Code
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 #define INF 0x3f3f3f
  8 struct node
  9 {
 10     int x,y,num;
 11 }al[110];
 12 char str[60][60];
 13 int f[60][60],dir[4][2]={0,1,0,-1,1,0,-1,0},n,m,w[110][110],visit[110],low[110],sum,ff[110][110];
 14 int judge(int i,int j)
 15 {
 16     if(i<1||i>n||j<1||j>m)
 17     return 0;
 18     if(str[i][j]=='#')
 19     return 0;
 20     return 1;
 21 }
 22 void bfs(int x,int y)
 23 {
 24     int i,j;
 25     queue<node>q;
 26     memset(f,0,sizeof(f));
 27     struct node st;
 28     st.x =x;
 29     st.y =y;
 30     f[st.x][st.y] = 1;
 31     st.num = 0;
 32     q.push(st);
 33     while(!q.empty())
 34     {
 35         struct node mt = q.front();
 36         int tx = mt.x;
 37         int ty = mt.y;
 38         int tnum = mt.num;
 39         q.pop();
 40         if(str[tx][ty]=='S'||str[tx][ty]=='A')
 41         {
 42             w[ff[x][y]][ff[tx][ty]] = tnum;
 43         }
 44         for(i = 0; i <= 3 ;i++)
 45         {
 46             int ti = dir[i][0]+tx;
 47             int tj = dir[i][1]+ty;
 48             if(!f[ti][tj]&&judge(ti,tj))
 49             {
 50                 f[ti][tj] = 1;
 51                 st.x = ti;
 52                 st.y = tj;
 53                 st.num = tnum+1;
 54                 q.push(st);
 55             }
 56         }
 57     }
 58 }
 59 void Prime(int n)
 60 {
 61      int i,j,k;
 62      memset(visit,0,sizeof(visit));
 63      visit[1] = 1;
 64      for(i = 2 ;i <= n ; i++)
 65          low[i] = w[1][i];
 66      for(i = 1 ; i <= n ; i++)
 67      {
 68          int max = INF;
 69          for(j = 1 ; j <= n ; j++)
 70              if(!visit[j]&&max>low[j])
 71                  max = low[k=j];
 72          if(max == INF)
 73              break;
 74          visit[k] = 1;
 75          sum+=max;
 76          for(j = 1 ; j <= n ; j++)
 77              if(!visit[j]&&low[j]>w[k][j])
 78              low[j] = w[k][j];
 79      }
 80 }
 81 int main()
 82 {
 83     int i,j,k,t,sx,sy;
 84     char ss[100];
 85     cin>>t;
 86     while(t--)
 87     {
 88         cin>>m>>n;
 89         gets(ss);
 90         memset(w,INF,sizeof(w));
 91         int g = 0;
 92         for(i = 1; i <= n ; i++)
 93         {
 94             getchar();
 95             for(j = 1; j <= m ; j++)
 96             {
 97                 scanf("%c",&str[i][j]);
 98                 if(str[i][j]=='A'||str[i][j]=='S')
 99                 {
100                     g++;
101                     ff[i][j]=g;
102                 }
103             }
104         }
105         int xx =0 ;
106         for(i = 1; i <= n ; i++)
107         for(j = 1 ; j <= m ; j++)
108            if(str[i][j]=='A'||str[i][j]=='S')
109                bfs(i,j);
110         sum = 0;
111         Prime(g);
112         cout<<sum<<endl;
113     }
114     return 0;
115 }