Borg Maze POJ

题意：

求把S和所有的A连贯起来所用的线的最短长度。。。

这道题。。不看discuss我能wa一辈子。。。

输入有坑。。。

然后，，，也没什么了。。。还有注意 一次bfs是可以求当前点到所有点最短距离的。。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = 100010, INF = 0x7fffffff;
int f[maxn], d[55][55];
int cnt, n, m;
int dis[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
char str[55][55], temp[maxn];
struct node
{
    int u, v, w;
}Node[maxn];

struct edge
{
    int x, y;
}Edge[maxn];

void add(int u, int v, int w)
{
    Node[cnt].u = u;
    Node[cnt].v = v;
    Node[cnt++].w = w;
}

void init()
{
    for(int i=0; i<maxn; i++) f[i] = i;
    cnt = 0;
}

int cmp(node a, node b)
{
    return a.w < b.w;
}

int find(int x)
{
   // return f[x]==x?x:(f[x] = find(f[x]));
    if(f[x] == x) return x;
    int r = f[x];
    while(r != f[r]) r = f[r];
    int i = x, j;
    while(i!=r)
    {
        j = f[i];
        f[i] = r;
        i = j;
    }
    return r;
}

void bfs(edge s)
{
    queue<edge> Q;
    mem(d, 0);
    Q.push(s);
    d[s.x][s.y] = 1;
    while(!Q.empty())
    {
        s = Q.front(); Q.pop();
        for(int i=0; i<4; i++)
        {
            edge t;
            t.x = s.x + dis[i][0];
            t.y = s.y + dis[i][1];
            if(t.x < 0 || t.x >= n || t.y < 0 || t.y >= m || d[t.x][t.y] || str[t.x][t.y] == '#') continue;
            d[t.x][t.y] = d[s.x][s.y] + 1;
            Q.push(t);
        }
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        int ans = 0;
        scanf("%d%d",&m,&n);
        gets(temp);
      //  getchar();
        for(int i=0; i<n; i++)
        {
            gets(str[i]);
            for(int j=0; j<m; j++)
            {
               if(str[i][j] == 'A' || str[i][j] == 'S')
                    Edge[++ans].x = i, Edge[ans].y = j;
            }
        }
        for(int i=1; i<=ans; i++)
        {
            bfs(Edge[i]);
            for(int j=i+1; j<=ans; j++)
                add(i, j, d[Edge[j].x][Edge[j].y] - 1);

        }
        sort(Node, Node+cnt, cmp);
        int sum = 0;
        for(int i=0; i<cnt; i++)
        {
            int r = find(Node[i].u);
            int l = find(Node[i].v);
            if(r == l) continue;
            f[r] = l;
            sum += Node[i].w;
        }

        printf("%d
",sum);

    }

    return 0;
}