使用多源BFS，
注意1：方向数组别写错
注意2：kruskal算法要用并查集来维护
注意3：n个节点的最小生成树只需要找到n-1条边就可以了
#include<bits/stdc++.h>
using namespace std;
const int N=105;
char mp[N][N];
int n;
int id[N][N];
int x[N],y[N];
struct node{int s,t,u; bool operator<(const node& a)const{return u>a.u; //小根堆 }
};
priority_queue<node> que; //node节点存放了一条边的权值和两个端点，优先队列有利于我kruskal
int dir[4][2]= {{0,1}, {0,-1}, {1,0}, {-1,0}};
void BFS(int x,int y){int vis[N][N];memset(vis,0,sizeof(vis));queue<node> que2; //这里node的s，t默认是目的点的坐标，起点x，y省略。 node temp = {x,y,0};que2.push(temp);vis[x][y]=1;while(!que2.empty()){node front = que2.front();que2.pop();if(id[front.s][front.t]!=-1){int qidian =id[x][y];int zhongdian=id[front.s][front.t];que.push({qidian,zhongdian,front.u});}for(int i=0;i<4;i++){int x1=front.s+dir[i][0];int y1=front.t+dir[i][1];if(x1>=0&&x1<n&&y1>=0&&y1<n&&!vis[x1][y1]){vis[x1][y1]=1;if(mp[x1][y1]=='#'){continue;}else{que2.push({x1,y1,front.u+1});}}}}
}
int fa[N];
int find(int i){if(fa[i] == i)return i;else return fa[i]=find(fa[i]);
}
int main(){scanf("%d",&n); for(int i=0;i<n;i++){scanf("%s",mp[i]);}memset(id,-1,sizeof(id));int cnt=0;for(int i=0;i<n;i++){for(int j=0;j<n;j++)if(mp[i][j]=='c'||mp[i][j]=='C'){id[i][j]=++cnt; //为楼标序号 ,序号从1开始 x[cnt]=i; //我要记录每栋楼的坐标 y[cnt]=j;} } //接下来想办法求出每栋楼到其他所有楼的最短距离，并插入到优先队列中for(int i=1;i<=cnt;i++ ) {BFS(x[i],y[i]);fa[i]=i;}int ans=0; //记录答案 int cnt2=0; //n个节点的最小生成树，找到n-1条边就可以了 while(cnt2<cnt-1){node front=que.top();// cout<<front.s<<" "<<front.t<<" "<<front.u<<endl;que.pop();int a=find(front.s);int b=find(front.t);if(a!=b){ans+=front.u; fa[a]=b;cnt2++;}}printf("%d",ans); return 0;
}