就这么做到了人生中第一道略有难度的组合题哈哈哈哈心里还有点小激动。
来认真写一发题解好了。
题目概述：
有一簇叫做Borg的外星生物，想要扫描整个迷宫建立与其所有下属的联系。迷宫有空格，代表能走的路，有#代表墙壁。有A代表生物，有S代表初始位置。从一个点出发，过程中可以随意分裂，但是行走方式只能是上下左右。然后我们要写一个程序，计算扫描的最短距离。也就是说，当有一个方式连接起来所有的点的时候（题中的A与S），计算这条线的最短距离。
这题坑，在col和row之后有一个不定大小的空格。
算法思想：
代码中有很多注释哟
出发点是无所谓的（有对称性嘛，不明白就去面壁）。
因为最终的目的是要把这些点都用一串线连接起来，所以是一个最小生成树的问题，那还是取用Prim算法。
但是此时这张图并没有被建立起来，我们的做法应该是要建立每一个点到其他点的距离矩阵，也就是代码中的dis[][]。
这时候问题又很熟悉，类似于之前做过的迷宫的最短路径，那么这个时候需要做的就是用bfs来遍历整张图，从一个点开始，往外扩张，遇到点就把当前扩张的次数记为从起始点到这个点的距离。
然后图建完了，直接套用prim的模板就好了。
关于很多数组的memset与全局变量初始化与否：
maze这个是代表迷宫的数组，每次都新读且有配套的col,row做限制，不必重设。
node这个东西要重设，因为每次不一样，且不会覆盖。
vis，dis都在bfs函数中起始的时候设定了。
cost无需重设因为其实被bfs覆盖更新。
used需要重设，理由同node。
min_cost无需重设因为prim开始时候会设为正无穷。
代码部分：
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int n, col, row,num; const int INF = 100000000;
char maze[55][55]; // 迷宫的图
int node[55][55]; // 如果该处并没有点的话记为0，否则1234依此类推
bool vis[55][55]; // 在每一次bfs中，记录i,j位置是否经历过
int dis[55][55]; // 在每一次bfs中，记录当前node所遍历到的位置
int cost[117][117]; // prim算法中，最终的两点之间的cost值
bool used[2500]; // prim算法中，点是否已经被加入集合
int min_cost[2500]; // prim算法中，集合到点的最近距离
struct point {
int x, y;
point(int a, int b) :x(a), y(b) {}
};
// 通过bfs来建立cost之间最小距离的关系
void bfs(int x, int y) {
memset(dis, 0, sizeof(dis));
memset(vis, 0, sizeof(vis));
queue<point> q;
q.push(point(x, y));
vis[x][y] = 1;
while (!q.empty()) {
point tmp = q.front();
q.pop();
if (node[tmp.x][tmp.y]) {
cost[node[x][y]][node[tmp.x][tmp.y]] = dis[tmp.x][tmp.y];
}
if (tmp.x + 1 < row && maze[tmp.x + 1][tmp.y] != '#' && !vis[tmp.x+1][tmp.y]) {
vis[tmp.x + 1][tmp.y] = 1;
q.push(point((tmp.x + 1), tmp.y));
dis[(tmp.x + 1)][tmp.y] = dis[tmp.x][tmp.y] + 1;
}
if (tmp.x - 1 >= 0 && maze[tmp.x - 1][tmp.y] != '#' && !vis[tmp.x - 1][tmp.y]) {
vis[tmp.x - 1][tmp.y] = 1;
q.push(point(tmp.x - 1, tmp.y));
dis[tmp.x - 1][tmp.y] = dis[tmp.x][tmp.y] + 1;
}
if (tmp.y + 1 < col && maze[tmp.x][tmp.y + 1] != '#' && !vis[tmp.x][tmp.y + 1]) {
vis[tmp.x][tmp.y + 1] = 1;
q.push(point(tmp.x, tmp.y + 1));
dis[tmp.x][tmp.y + 1] = dis[tmp.x][tmp.y] + 1;
}
if (tmp.y - 1 >= 0 && maze[tmp.x][tmp.y - 1] != '#' && !vis[tmp.x][tmp.y - 1]) {
vis[tmp.x][tmp.y - 1] = 1;
q.push(point(tmp.x, tmp.y - 1));
dis[tmp.x][tmp.y - 1] = dis[tmp.x][tmp.y] + 1;
}
}
}
// prim算法求最小生成树
int prim() {
int res = 0;
memset(used, 0, sizeof(used));
for (int i = 1; i < num; i++) {
min_cost[i] = INF;
}
min_cost[1] = 0;
while (true) {
int v = -1;
for (int u = 1; u < num; u++) {
if (!used[u] && (v == -1 || min_cost[u] < min_cost[v])) v = u;
}
if (v == -1) break;
used[v] = 1;
res += min_cost[v];
for (int u = 1; u < num; u++) {
min_cost[u] = min(min_cost[u], cost[v][u]);
}
}
return res;
}
int main() {
cin >> n;
for (int k = 0; k < n; k++) {
cin >> col >> row;
char tmp[60];
gets(tmp);
memset(node, 0, sizeof(node));
num = 1;
for (int i = 0; i < row; i++) {
gets(maze[i]);
for (int j = 0; j < col; j++) {
if (maze[i][j] == 'A' || maze[i][j] == 'S') {
node[i][j] = num++;
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (node[i][j]) bfs(i, j);
}
}
cout << prim() << endl;
}
return 0;
}