http://acm.pku.edu.cn/JudgeOnline/problem?id=3026

 这道题的输入数据及其猥琐,有很多无用的空格。。。
其他还是没什么的,只要BFS处理下两点间的距离,然后MST一下。。。

// 3026 Borg Maze
// Time Limit: 1000MS        Memory Limit: 65536K
// Total Submissions: 2827        Accepted: 888

#include
<iostream>
#include
<queue>
#define MAXN 105
#define N 55
#define INF 10000000
using namespace std;
struct node
{
    
int x,y;
    
int step;
}
;
int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}};
char maze[N][N];
bool vis[N][N];
int g[MAXN][MAXN],v[N][N];
node d[MAXN];
int n,m,cnt;
void BFS( node a )
{
    
int i,x,y,nx,ny,step;
    node p;
    queue
<node> que;
    memset( vis, 
falsesizeof(vis) );
    que.push( a );
    vis[a.x][a.y]
=true;
    
while!que.empty( ) )
    
{
        p
=que.front( );
        que.pop( );
        x
=p.x,y=p.y,step=p.step+1;
        
for( i=0; i<4; i++ )
        
{
            nx
=x+dir[i][0],ny=y+dir[i][1];
            
if( nx<&& nx>=0 && ny<&& ny>=0 && !vis[nx][ny])
            
{
                
if( maze[nx][ny]=='S' || maze[nx][ny]=='A' )
                
{
                    g[v[a.x][a.y]][v[nx][ny]]
=g[v[nx][ny]][v[a.x][a.y]]=step;
                    p.x
=nx,p.y=ny,p.step=step;
                    que.push( p );
                    vis[nx][ny]
=true;
                }

                
if( maze[nx][ny]==' ' )
                
{
                    p.x
=nx,p.y=ny,p.step=step;
                    que.push( p );
                    vis[nx][ny]
=true;
                }

            }

        }

    }

}


void create_graph( )
{
    
int i,j;
    
for( i=0; i<m; i++ )
        gets( maze[i] );
    cnt
=0;
    
for( i=0; i<m; i++ )
        
for( j=0; j<n; j++ )
            
if( maze[i][j]=='A' || maze[i][j]=='S' )
                d[cnt].x
=i,d[cnt].y=j,d[cnt].step=0,v[i][j]=cnt++;
    
for( i=0; i<cnt; i++ )
        
for( g[i][i]=0, j=i+1; j<cnt; j++ )
            g[i][j]
=g[j][i]=INF;
    
for( i=0; i<cnt; i++ )
        BFS( d[i] );
}


int prim( )
{
    
int i,j,k,min,ans;
    
int dis[MAXN];
    
for( i=0; i<cnt; i++ )
        dis[i]
=g[0][i];
    ans
=0;
    
for( i=1; i<cnt; i++ )
    
{
        min
=INF,k=-1;
        
for( j=0; j<cnt; j++ )
            
if( dis[j] && dis[j]<min )
                min
=dis[j],k=j;
        ans
+=min;
        dis[k]
=0;
        
for( j=0; j<cnt; j++ )
            
if( dis[j] && g[k][j]<dis[j] )
                dis[j]
=g[k][j];
    }

    
return ans;
}


int main( )
{
    
int ans,t;
    
char c[100];
    scanf(
"%d",&t);
    
while( t-- )
    
{
        scanf(
"%d%d",&n,&m);
        gets( c );
        create_graph( );
        ans
=prim( );
        printf(
"%d\n",ans);
    }

    
return 0;
}