题目大意
求把所有的S与A连通所需要的边长。题目有一个坑点就是输入m和n的那一行后面可能还有字符(可能还不止一个？？？，所以需要过滤一下。
解题思路1
这题很容易看出来是让求一棵最小生成树的大小，我们任选一个点做最小生成树的起点都没有问题所以A和S其实是一样的。
但是题目并没有给出边，而是直接给了一个地图。那么我们可以求出所有点A到其他的点A的最小距离，就得到了一个使任意两个点A两两相连的图。对于我们所得到的图，就可以直接跑最小生成树得到答案了。
代码1
const int maxn = 1e2+10;
struct E {
int u, v, w;
bool operator < (const E &a) const {
return w < a.w;
}
}; vector<E> e;
char g[maxn][maxn];
bool vis[maxn][maxn];
int num[maxn][maxn], tot, p[maxn*maxn];
int n, m; int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
void bfs(int sx, int sy) {
zero(vis); queue<E> pq;
pq.push({sx,sy,0});
if (!num[sx][sy]) num[sx][sy] = tot++;
while(!pq.empty()) {
E t = pq.front(); pq.pop();
if (vis[t.u][t.v]) continue;
if ((g[t.u][t.v]=='A'||g[t.u][t.v]=='S') && num[sx][sy]!=num[t.u][t.v]) {
if (!num[t.u][t.v]) num[t.u][t.v] = tot++;
e.push_back({num[sx][sy],num[t.u][t.v],t.w});
}
vis[t.u][t.v] = true;
for (int i = 0; i<4; ++i) {
int xx = t.u+dx[i], yy = t.v+dy[i];
if (xx>=0&&yy>=0&&xx<n&&yy<m&&!vis[xx][yy]&&g[xx][yy]!='#')
pq.push({xx,yy,t.w+1});
}
}
}
int find(int x) {
if (p[x]!=x) p[x] = find(p[x]);
return p[x];
}
int kruskal() {
int sum = 0;
sort(e.begin(),e.end());
for (int i = 0; i<maxn*maxn; ++i) p[i] = i;
int sz = e.size();
for (int i = 0; i<sz; ++i)
if (find(e[i].u)!=find(e[i].v)) {
p[find(e[i].u)] = find(e[i].v);
sum += e[i].w;
}
return sum;
}
int main() {
int t; scanf("%d",&t);
while(t--) {
tot = 0; zero(num);
scanf("%d%d",&m,&n);char ch[2000]; fgets(ch,1999,stdin);
for (int i = 0; i<n; ++i) scanf("%[^
]%*c",g[i]);
for (int i = 0; i<n; ++i)
for (int j = 0; j<m; ++j)
if (g[i][j]=='S'||g[i][j]=='A') bfs(i,j);
printf("%d
",kruskal()); e.clear();
}
return 0;
}
解题思路2
其实我们也可以直接跑bfs来求解。思路与prim算法类似，我们从任意一个A出发，找到所有离他最近的点A，然后从其他的点A出发，找到离它们最近的其他的点A。
但是具体实现起来可能有些问题，如何比如说从点(A_1)到了点(A_2)，对于离(A_2)最近的点(A_3)，如何确保它先被(A_2)访问到呢？我们可以用优先队列存储每个节点和每个节点到离它最近的点A的距离，如果从一个点(A_1)到达了另外一个点(A_2)，那么就把与(A_2)相邻的点更新成它们到(A_2)的距离而不是到(A_1)的距离就行了。
代码2
const int maxn = 5e1+10;
struct E {
int sx,sy,ex,ey,w;
bool operator < (const E &a) const {
return w > a.w;
}
};
char g[maxn][maxn];
bool num[maxn][maxn]; //标记被访问过的A或者S
int n, m, d[maxn][maxn]; //d[]表示某个点到离它最近的A或者S的距离
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
int bfs(int x, int y) {
int sum = 0;
zero(num); INF(d); d[x][y] = 0;
priority_queue<E> pq;
pq.push({x,y,x,y,0});
if (!num[x][y]) num[x][y] = true;
while(!pq.empty()) {
E t = pq.top(); pq.pop();
if (d[t.ex][t.ey]<t.w) continue;
if ((g[t.ex][t.ey]=='A'||g[t.ex][t.ey]=='S') && !num[t.ex][t.ey]) {
num[t.ex][t.ey] = true;
sum += t.w;
t = {t.ex,t.ey,t.ex,t.ey,0};
}
for (int i = 0; i<4; ++i) {
int xx = t.ex+dx[i], yy = t.ey+dy[i];
if (xx>=0&&yy>=0&&xx<n&&yy<m&&g[xx][yy]!='#'&&d[xx][yy]>t.w+1) {
d[xx][yy] = t.w+1;
pq.push({t.sx,t.sy,xx,yy,d[xx][yy]});
}
}
}
return sum;
}
int main() {
int t; scanf("%d",&t);
while(t--) {
scanf("%d%d",&m,&n);char ch[2000]; fgets(ch,1999,stdin);
for (int i = 0; i<n; ++i) scanf("%[^
]%*c",g[i]);
for (int i = 0; i<n; ++i)
for (int j = 0; j<m; ++j)
if (g[i][j]=='S'||g[i][j]=='A') {
printf("%d
",bfs(i,j));
goto out;
}
out:;
}
return 0;
}