http://poj.org/problem;jsessionid=A0F3392F460475E0058F93E009D6BFC3?id=3026
2 6 5 ##### #A#A## # # A# #S ## ##### 7 7 ##### #AAA### # A# # S ### # # #AAA### #####
8 11
题意：
求有字母的各个点都彼此连接起来的最短步数。
思路：
BFS+最小生成树，刚开始就是不知道该怎样下手写
既然每一个 S 或 A 处才可以分裂，并且只能让其中一个行走，求最小的路径长度，便是一棵包含所有 S 或 A 点的树。
那么，首先通过BFS枚举每一个点到其他点的最短路径长度，若距离小于初始值，则更新该距离，然后建立这样一个完全图，然后在这一个完全图中求最小生成树即可。
注意，该题在输入x,y之后可能会出现很多空格哦！用一般的%*c和getchar()都会失效，所以我们用gets(str)，故WA了好多次。
根据题意的“分离”规则，重复走过的路不再计算
因此当使用prim算法求L的长度时，根据算法的特征恰好不用考虑这个问题（源点合并很好地解决了这个问题），L就是最少生成树的总权值W
由于使用prim算法求在最小生成树，因此无论哪个点做起点都是一样的，（通常选取第一个点），因此起点不是S也没有关系。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <math.h> 6 #include <algorithm> 7 #include <vector> 8 #include <stack> 9 #include <queue> 10 #include <set> 11 #include <map> 12 #include <sstream> 13 const int INF=0x3f3f3f3f; 14 typedef long long LL; 15 const int mod=1e9+7; 16 //const double PI=acos(-1); 17 #define Bug cout<<"---------------------"<<endl 18 const int maxn=1e5+10; 19 using namespace std; 20 21 int NT[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; 22 char MP[110][110];//存放迷宫 23 int G[110][110];//存放图 24 int number[110][110];//存放迷宫中S或A点所对应的编号 25 int lowval[110];//辅助贪心数组 26 int VIS[110][110];//BFS时判断迷宫的某个位置是否走过 27 int vis[110];//Prim时判断顶点是否加入最小生成树 28 int n,m; 29 30 struct node 31 { 32 int x; 33 int y; 34 int step; 35 }; 36 37 void BFS(int u,int x,int y) 38 { 39 memset(VIS,0,sizeof(VIS)); 40 node begins,next; 41 begins.x=x; 42 begins.y=y; 43 begins.step=0; 44 queue<node> qe; 45 qe.push(begins); 46 VIS[x][y]=1; 47 while(qe.size()) 48 { 49 node now=qe.front(); 50 qe.pop(); 51 if(MP[now.x][now.y]==‘A‘||MP[now.x][now.y]==‘S‘) 52 G[u][number[now.x][now.y]]=now.step; 53 for(int i=0;i<4;i++) 54 { 55 next.x=now.x+NT[i][0]; 56 next.y=now.y+NT[i][1]; 57 if(next.x>=0&&next.x<m&&next.y>=0&&next.y<n&&MP[next.x][next.y]!=‘#‘&&!VIS[next.x][next.y]) 58 { 59 VIS[next.x][next.y]=1; 60 next.step=now.step+1; 61 qe.push(next); 62 } 63 } 64 } 65 } 66 67 int Prim(int N,int st) 68 { 69 memset(vis,0,sizeof(vis)); 70 int sum=0; 71 for(int i=0;i<N;i++) 72 lowval[i]=G[st][i]; 73 vis[st]=1; 74 for(int i=0;i<N-1;i++) 75 { 76 int t=-1; 77 int MIN=INF; 78 for(int j=0;j<N;j++) 79 { 80 if(!vis[j]&&lowval[j]<MIN) 81 { 82 MIN=lowval[j]; 83 t=j; 84 } 85 } 86 sum+=MIN; 87 vis[t]=1; 88 for(int j=0;j<N;j++) 89 { 90 if(!vis[j]&&lowval[j]>G[t][j]) 91 lowval[j]=G[t][j]; 92 } 93 } 94 return sum; 95 } 96 97 98 int main() 99 { 100 int T; 101 scanf("%d",&T); 102 while(T--) 103 { 104 scanf("%d %d ",&n,&m);//记得最后加上一个空格或者\n过滤掉输入中的空格 105 int k=0; 106 for(int i=0;i<m;i++) 107 { 108 gets(MP[i]); 109 for(int j=0;j<n;j++) 110 { 111 if(MP[i][j]==‘A‘||MP[i][j]==‘S‘) 112 number[i][j]=k++; 113 } 114 } 115 for(int i=0;i<m;i++) 116 { 117 for(int j=0;j<n;j++) 118 { 119 if(i==j) 120 G[i][j]=0; 121 else G[i][j]=INF; 122 } 123 } 124 for(int i=0;i<m;i++) 125 { 126 for(int j=0;j<n;j++) 127 { 128 if(MP[i][j]==‘A‘||MP[i][j]==‘S‘) 129 BFS(number[i][j],i,j); 130 } 131 } 132 printf("%d\n",Prim(k,0)); 133 } 134 }
原文：https://www.cnblogs.com/jiamian/p/11737596.html