> 
> #include<stdio.h>
> #include<string.h>
> char map[105][105];
> int id[105][105];
> char m[105][105];
> int cost[105][105];
> int x, y;
> const int MAX = 200000000;
> int dx[13505], dy[13505];
> int dxx[4] = { 0, 0, 1, -1 };
> int dyy[4] = { 1, -1, 0, 0 };
> int len;
> int v;
> void bfs( int xx, int yy )
> {
>     int head = 0, tail = 1, ttail, step = 0;
>     int i, k, r, xxx, yyy;
>     dx[0] = xx;
>     dy[0] = yy;
>     m[xx][yy] = '#';
>     while( head < tail )
>     {
>         ttail = tail;
>         step++;
>         for( i = head; i < tail; i++ )
>         {
>             for( r = 0; r < 4; r++ )
>             {
>                 xxx = dx[i]+dxx[r];
>                 yyy = dy[i]+dyy[r];
>                 
>                 if( xxx >= 0 && xxx < y && yyy >= 0 && yyy < x && m[xxx][yyy] != '#' )
>                 {
>                     dx[ttail] = xxx;
>                     dy[ttail++] = yyy;
>                     if( m[xxx][yyy] == 'A' )
>                     {
>                         cost[id[xx][yy]][id[xxx][yyy]] = step;
>                         cost[id[xxx][yyy]][id[xx][yy]] = step;
>                     }
>                     m[xxx][yyy] = '#';
>                 }
>             }
>         }
>         head = tail;
>         tail = ttail;
>     }
> }
> 
> void MST()
> {
>     int mincost[105], minans, min;
>     int i, j, k;
>     minans = 0;
>     
>     for( i = 1; i <= len; i++ )
>     {
>         mincost[i] = cost[v][i];
>     }
>     mincost[v] = -1;
>     for( i = 1; i <= len; i++ )
>     {
>         min = MAX;
>         k = 0;
>         for( j = 1; j <= len; j++ )
>         {
>             if( mincost[j] > 0 && min > mincost[j] )
>             {
>                 min = mincost[j];
>                 k = j;
>             }
>         }
>         if( min == MAX )break;
>         mincost[k] = -1;
>         minans += min;
>         
>         for( j = 1; j <= len; j++ )
>         {
>             if( cost[k][j] < mincost[j] )
>             {
>                 mincost[j] = cost[k][j];
>             }
>         }
>     }
>     printf( "%d\n", minans );
> }
> 
> 
> int main()
> {
>     int i, j, r, k;
>     int kcase;
>     scanf( "%d", &kcase );
>     while( kcase-- )
>     {
>         scanf( "%d %d", &x, &y );
>         len = 0;
>         memset( id, 0, sizeof( id ) );
>         getchar();//这里用gets的好 后面好多空格
>         for( i = 0; i < y; i++ )
>         {
>             gets(map[i]);
>         }
>         for( i = 0; i < y; i++ )
>         {
>             for( j = 0; j < x; j++ )
>             {
>                 if( map[i][j] == 'S' )
>                 {
>                     map[i][j] = 'A';
>                     id[i][j] = ++len;
>                     v = len;
>                 }
>                 else if( map[i][j] == 'A' )
>                 {
>                     id[i][j] = ++len;
>                 }
>             }
>         }
>         memset( cost, 0, sizeof( cost ) );
>         for( i = 0; i < y; i++ )
>         {
>             for( j = 0; j < x; j++ )
>             {
>                 if( map[i][j] == 'A' )
>                 {
>                     for( k = 0; k < y; k++ )
>                         for( r = 0; r < x; r++ )
>                             m[k][r] = map[k][r]; 
>                     
>                     bfs( i, j );
>                 }
>             }
>         }
>         MST();
>     }
>     return 0;
> }
>