#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();
        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;
}

• Re: 哪位大牛帮帮忙啊，一直WA....... 给几组BT的数据吧 (3554) 20053565 2007-12-25 12:09:20
• Re: 哪位大牛帮帮忙啊，一直WA....... 给几组BT的数据吧 (12) zab08 2008-04-11 08:53:18