Borg Maze poj3026

  首先這道題不得不讓我吐槽下，測試數據太無語了，在輸入列和行後，後面竟然還會輸空格，所以不能用getchar（）去處理'\n'，只能用gets（），這樣一次性就可以處理掉空格和'\n'。

    然後再說說本題的思想吧，我是先對每個A或S用一次BFS，求出它與其它的A或S的最短距離，然後再以這些A或S建圖，求一次最小生成樹，然後把所有的邊權相加

[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
struct st 
{ 
    int x,y,step; 
}w,tmp; 
st q[2505]; 
const int INF=100000000; 
int map[55][55]; 
bool visit[55][55]; 
bool visit1[105]; 
int dist[105][105]; 
int dirt[4][2]={0,1,0,-1,1,0,-1,0}; 
int d[105]; 
int t,n,m,num; 
 
bool ok(int x,int y) 
{ 
    return x>=0&&x<n&&y>=0&&y<m&&map[x][y]!=-1; 
} 
 
void BFS(int u) 
{ 
    memset(visit,false,sizeof(visit)); 
    visit[w.x][w.y]=true; 
    int front=0,rear=0; 
    q[rear++]=w; 
    while(front<rear) 
    { 
        w=q[front++]; 
        if(map[w.x][w.y]>0) 
            dist[u][map[w.x][w.y]]=w.step; 
        for(int i=0;i<4;i++) 
        { 
            tmp.x=w.x+dirt[i][0]; 
            tmp.y=w.y+dirt[i][1]; 
            tmp.step=w.step+1; 
            if(ok(tmp.x,tmp.y)&&!visit[tmp.x][tmp.y]) 
            { 
                visit[tmp.x][tmp.y]=true; 
                q[rear++]=tmp; 
            } 
        } 
    } 
} 
 
int main() 
{ 
    int i,j,k,sum; 
    scanf("%d",&t); 
    char tmp[100]; 
    while(t--) 
    { 
        num=0; 
        scanf("%d%d",&m,&n); 
        //getchar(); 
        gets(tmp); 
        for(i=0;i<n;i++) 
        { 
            gets(tmp); 
            for(j=0;j<m;j++) 
            { 
                if(tmp[j]=='S'||tmp[j]=='A') 
                    map[i][j]=++num; 
                else if(tmp[j]==' ') 
                    map[i][j]=0; 
                else 
                    map[i][j]=-1; 
            } 
        } 
        //計算任意兩個alien的最短距離 
        for(i=0;i<n;i++) 
            for(j=0;j<m;j++) 
                if(map[i][j]>0) 
                { 
                    w.x=i;w.y=j;w.step=0; 
                    BFS(map[i][j]); 
                } 
 
        //Prim 
        for(i=0;i<=num;i++) 
        { 
            visit1[i]=false; 
            d[i]=INF; 
        } 
        d[1]=0; 
        for(i=1;i<=num;i++) 
        { 
            k=0; 
            for(j=1;j<=num;j++) 
                if(d[j]<d[k]&&!visit1[j]) 
                    k=j; 
            if(k==0) 
                break; 
            visit1[k]=true; 
            for(j=1;j<=num;j++) 
                if(!visit1[j]&&dist[k][j]<d[j]) 
                    d[j]=dist[k][j]; 
        } 
        sum=0; 
        for(j=1;j<=num;j++) 
            sum+=d[j]; 
        printf("%d\n",sum); 
    } 
    return 0; 
}