1 //Memory: 220K        Time: 32MS  2 #include <iostream>  3 #include <cstdio>  4 #include <string>  5 #include <cstring>  6 #include <queue>  7   8 using namespace std;  9  10 const int maxn = 52; 11 const int max_alien = 101; 12 char maze[maxn][maxn]; 13 int m[maxn][maxn]; 14 int g[max_alien][max_alien]; 15 int vis[maxn][maxn]; 16 int v[max_alien + 1]; 17 int d[max_alien + 1]; 18 int alien; 19 int test, x, y; 20 int si[max_alien + 1], sj[max_alien + 1]; 21 int step[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 22  23 struct node 24 { 25     int i; 26     int j; 27     int d; 28     void set(int ii, int jj) 29     { 30         i = ii; 31         j = jj; 32         d = 0; 33     } 34 }n1, n2; 35  36 queue<struct node> q; 37  38 void bfs(int num, int i, int j) 39 { 40     memset(vis, 0, sizeof(vis)); 41     int t = alien - num; 42     while ( !q.empty() ) q.pop(); 43     n1.set(i, j); 44     q.push(n1); 45  46     while ( !q.empty() && t > 0 ){ 47         n1 = q.front(); 48         q.pop(); 49  50         for (int i = 0; i < 4; i++){ 51             n2.set(n1.i + step[i][0], n1.j + step[i][1]); 52             /*if (n2.i < 0 || n2.j < 0 ||)*/ 53             if (maze[n2.i][n2.j] == ‘#‘ || vis[n2.i][n2.j]) continue; 54              55             vis[n2.i][n2.j] = 1; 56             n2.d = n1.d + 1; 57  58             if (m[n2.i][n2.j] > num){ 59                 t--; 60                 g[num][ m[n2.i][n2.j] ] = g[ m[n2.i][n2.j] ][num] = n2.d; 61             } 62  63             q.push(n2); 64         } 65     } 66      67 } 68  69 int prim() 70 { 71     memset(v, 0, sizeof(v)); 72     v[0] = 1; 73     int ret = 0; 74     for (int i = 1; i <= alien; i++) 75         d[i] = g[0][i]; 76  77     for (int i = 0; i < alien; i++) { 78  79         int _min = 3000, ix; 80         for (int j = 1; j <= alien; j++) { 81             if ( !v[j] && d[j] < _min){ 82                 _min = d[j]; 83                 ix = j; 84             } 85         } 86         v[ix] = 1; 87         ret += d[ix]; 88  89         for (int j = 1; j <= alien; j++){ 90             if (!v[j] && d[j] > g[ix][j]) 91                 d[j] = g[ix][j]; 92         } 93     } 94     return ret; 95 } 96  97 int main() 98 { 99     scanf("%d", &test);100     while (test--){101         memset(m, 0, sizeof(m));102         scanf("%d%d", &x, &y);103         gets(maze[0]);104         alien = 0;105         for (int i = 0; i < y; i++)106             gets(maze[i]);107         for (int i = 0; i < y; i++){108             for (int j = 0; j < x; j++){109                 if (maze[i][j] == ‘S‘){110                     si[0] = i; 111                     sj[0] = j;112                 }113                 else if (maze[i][j] == ‘A‘) {114                     m[i][j] = ++alien;115                     si[alien] = i;116                     sj[alien] = j;117                 }118             }119         }120 121         memset(g, 0, sizeof(g));122         for (int i = 0; i <= alien; i++){123             bfs(i, si[i], sj[i]);124         }125 126         int ans = prim();127 128         printf("%d\n", ans);129     }130     return 0;131 }