题意：来自神姐http://blog.csdn.net/lyy289065406/article/details/6645991
在一个y行 x列的迷宫中，有可行走的通路空格’ ‘，不可行走的墙’#’，还有两种英文字母A和S，现在从S出发，要求用最短的路径L连接所有字母，输出这条路径L的总长度。
一格的长度为1，而且移动的方法只有上、下、左、右，
所以在无任何墙的情况下（但“墙#”是必须考虑的，这里只是为了说明）
任意两个字母之间的距离就是直接把 横坐标之差 加上 纵坐标之差
注意的是，可行的路为 字母 和 空格
不可行的路为 # 和 矩阵范围之外
根据题意的“分离”规则，重复走过的路不再计算
因此当使用prim算法求L的长度时，根据算法的特征恰好不用考虑这个问题（源点合并很好地解决了这个问题），L就是最少生成树的总权值W
由于使用prim算法求在最小生成树，因此无论哪个点做起点都是一样的，（通常选取第一个点），因此起点不是S也没有关系
所以所有的A和S都可以一视同仁，看成一模一样的顶点就可以了
最后要注意的就是 字符的输入
cin不读入空字符（包括 空格，换行等）
gets读入空格，但不读入换行符）
剩下的问题关键就是处理 任意两字母间的最短距离，由于存在了“墙#” ，这个距离不可能单纯地利用坐标加减去计算，必须额外考虑，推荐用BFS（广搜、宽搜），这是本题的唯一难点，因为prim根本直接套用就可以了
求 任意两字母间的最短距离 时不能直接用BFS求，
1、必须先把矩阵中每一个允许通行的格看做一个结点（就是在矩阵内所有非#的格都作为图M的一个顶点），对每一个结点i，分别用BFS求出它到其他所有结点的权值（包括其本身，为0），构造结点图M；
2、然后再加一个判断条件，从图M中抽取以字母为顶点的图，进而构造字母图N
这个判定条件就是当结点图M中的某点j为字母时，把i到j的权值再复制（不是抽离）出来，记录到字母图N的邻接矩阵中
3、剩下的就是对字母图N求最小生成树了
分析：这题关键是建图，图建好了就是套用prim就行了。
嗨，我不太会bfs啊。
View Code
// I'm the Topcoder //C #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> #include <time.h> //C++ #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <cctype> #include <stack> #include <string> #include <list> #include <queue> #include <map> #include <vector> #include <deque> #include <set> using namespace std; //*************************OUTPUT************************* #ifdef WIN32 #define INT64 "%I64d" #define UINT64 "%I64u" #else #define INT64 "%lld" #define UINT64 "%llu" #endif //**************************CONSTANT*********************** #define INF 0x3f3f3f3f #define eps 1e-8 #define PI acos(-1.) #define PI2 asin (1.); typedef long long LL; //typedef __int64 LL; //codeforces typedef unsigned int ui; typedef unsigned long long ui64; #define MP make_pair typedef vector<int> VI; typedef pair<int, int> PII; #define pb push_back #define mp make_pair //***************************SENTENCE************************ #define CL(a,b) memset (a, b, sizeof (a)) #define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b)) #define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c)) //****************************FUNCTION************************ template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); } template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; } template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; } // aply for the memory of the stack //#pragma comment (linker, "/STACK:1024000000,1024000000") //end #define maxn 110 //字符矩阵 char mat[110][110]; int x,y,n,k; struct Node{ int x,y; }; int dis[maxn][maxn];//A之间的距离 int vis[maxn][maxn];//广搜过程中记录点是否访问过 int dir[4][2]={{0,1},{-1,0},{0,-1},{1,0}};//方向数组 int index[maxn][maxn];//记录某个位置对应node节点的下标 int dd[maxn][maxn];//广搜的过程中记录距离 int lowcost[maxn];//记录保存的最短距离lowcost int visited[maxn]; queue<Node> q; int sumweight; int nearvex[maxn]; bool is_ok(int a,int b){ if(a>=0&&a<y&&b>=0&&b<y){ return true; } return false; } void bfs(Node nd){ q.push(nd); memset(vis,0,sizeof(vis)); dd[nd.x][nd.y]=0; vis[nd.x][nd.y]=1; while(!q.empty()){ Node tmp=q.front(); q.pop(); for(int i=0;i<4;i++){ int xx=tmp.x+dir[i][0];//下一个方向 int yy=tmp.y+dir[i][1]; if(is_ok(xx,yy)&&(mat[xx][yy]=='A'||mat[xx][yy]==' '||mat[xx][yy]=='S')&&!vis[xx][yy]){ dd[xx][yy]=dd[tmp.x][tmp.y]+1;//合法的结点，距离+1 vis[xx][yy]=1;//标记一下,表示访问过 if(mat[xx][yy]=='A'||mat[xx][yy]=='S'){ dis[index[nd.x][nd.y]][index[xx][yy]]=dd[xx][yy]; dis[index[xx][yy]][index[nd.x][nd.y]]=dd[xx][yy]; } Node ne; ne.x=xx; ne.y=yy; q.push(ne); } } } } //起点设置为0 void prim(){ //从顶点u0出发执行普里姆算法 sumweight=0;//生成树的权值 for(int i=1;i<k;i++){ //初始化lowcost[]数组和neartxt数组 lowcost[i]=dis[0][i]; nearvex[i]=0; } nearvex[0]=-1; for(int i=1;i<k;i++){ int min=INF; int v=-1; //在lowcoat数组的nearvex[]值为-1的元素中找最小值 for(int j=1;j<k;j++){ if(nearvex[j]!=-1&&lowcost[j]<min){ v=j; min=lowcost[j]; } } if(v!=-1){ //v==-1表示没找到权值最小的边 // printf("%d %d %d\n",nearvex[v],v,lowcost[v]); nearvex[v]=-1; sumweight+=lowcost[v]; for(int j=1;j<k;j++){ if(nearvex[j]!=-1&&dis[v][j]<lowcost[j]){ lowcost[j]=dis[v][j]; nearvex[j]=v; } } } } printf("%d\n",sumweight); } int main(){ char aa[maxn]; while(scanf("%d",&n)!=EOF){ while(n--){ k=0;//k记录结点的个数 scanf("%d%d",&x,&y); gets(aa); for(int i=0;i<y;i++){ for(int j=0;j<x;j++){ scanf("%c",&mat[i][j]); if(mat[i][j]=='A'||mat[i][j]=='S'){ index[i][j]=k;//记录某个位置对应node节点的下标 k++; } } getchar(); } //初始化距离 for(int i=0;i<k;i++){ for(int j=0;j<k;j++){ dis[i][j]=((i==j)?0:INF); } } //进入bfs for(int i=0;i<y;i++){ for(int j=0;j<x;j++){ if(mat[i][j]=='A'||mat[i][j]=='S'){//只要把合法的且要计算距离的记录下来就行了。 Node tmp;//结构体变量 tmp.x=i; tmp.y=j; bfs(tmp); } } } prim(); // printf("%d\n",prim(1)); } } return 0; }