题目链接：
https://vjudge.net/problem/POJ-3026
题目大意：
在一个y行 x列的迷宫中，有可行走的通路空格’ ‘，不可行走的墙’#’，还有两种英文字母A和S，现在从S出发，要求用最短的路径L连接所有字母，输出这条路径L的总长度。
思路：
先BFS预处理出所有的字母之间的距离，然后用prim模板
超级坑的是这里得用gets()吃掉回车符，用getchar()会WA
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<sstream>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pair;
const int maxn = 1e2 + ;
const int INF = 0x3f3f3f3f;
int dir[][] = {,,,,-,,,-};
int T, n, m, x;
int Map[maxn][maxn];//存图
int lowcost[maxn], mst[maxn];
void prim(int u, int n)//最小生成树起点
{
int sum_mst = ;//最小生成树权值
for(int i = ; i < n; i++)//初始化两个数组
{
lowcost[i] = Map[u][i];
mst[i] = u;
}
mst[u] = -;//设置成-1表示已经加入mst
for(int i = ; i < n; i++)
{
int minn = INF;
int v = -;
//在lowcost数组中寻找未加入mst的最小值
for(int j = ; j < n; j++)
{
if(mst[j] != - && lowcost[j] < minn)
{
v = j;
minn = lowcost[j];
}
}
if(v != -)//v=-1表示未找到最小的边,
{//v表示当前距离mst最短的点
//printf("%d %d %d\n", mst[v], v, lowcost[v]);//输出路径
mst[v] = -;
sum_mst += lowcost[v];
for(int j = ; j < n; j++)//更新最短边
{
if(mst[j] != - && lowcost[j] > Map[v][j])
{
lowcost[j] = Map[v][j];
mst[j] = v;
}
}
}
}
//printf("weight of mst is %d\n", sum_mst);
cout<<sum_mst<<endl;
}
string s[];
vector<Pair>a;
int vis[][];
void bfs(int u, int x, int y)//BFS预处理，将x，y为起点进行遍历，求出每个点离当前点距离，更新出Map距离出来
{
queue<Pair>q;
q.push(Pair(x, y)); memset(vis, -, sizeof(vis));
vis[x][y] = ;
while(!q.empty())
{
Pair now = q.front();
q.pop();
for(int i = ; i < ; i++)
{
int xx = now.first + dir[i][];
int yy = now.second + dir[i][];
if(xx >= && xx < n && yy >= && yy < m && s[xx][yy] != '#' && vis[xx][yy] == -)
{
vis[xx][yy] = vis[now.first][now.second] + ;
q.push(Pair(xx, yy));
}
}
}/*
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)cout<<vis[i][j]<<" ";
cout<<endl;
}*/
for(int i = ; i < a.size(); i++)
{
if(i == u)continue;
Map[u][i] = vis[a[i].first][a[i].second];
}
}
int main()
{
cin >> T;
getchar();
while(T--)
{
for(int i = ; i < ; i++)s[i].clear();
char cc[];
cin >> m >> n;
gets(cc);
a.clear();
for(int i = ; i < n; i++)
{
getline(cin, s[i]);
for(int j = ; j < m; j++)
if(s[i][j] == 'S' || s[i][j] == 'A')
a.push_back(Pair(i, j));
}
for(int i = ; i < a.size(); i++)
{
for(int j = ; j < a.size(); j++)
{
if(i == j)Map[i][j] = ;
else Map[i][j] = INF;
}
}
for(int i = ; i < a.size(); i++)
bfs(i, a[i].first, a[i].second);
/*for(int i = 0; i < a.size(); i++)
{
for(int j = 0; j < a.size(); j++)
{
cout<<Map[i][j]<<" ";
}
cout<<endl;
}*/
prim(, a.size());
}
return ;
}