| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 12032 | Accepted: 3932 |
Description
Input
Output
Sample Input
2 6 5 ##### #A#A## # # A# #S ## ##### 7 7 ##### #AAA### # A# # S ### # # #AAA### #####
Sample Output
8 11
题意：求输入图中‘S‘点到所有‘A‘点的最小距离。
题解：这个题出的很好，要把一幅图转换为另外一幅图，用BFS把每一个点到其余所有的点的距离全部求一遍，然后按照点的下标构造一副新的图。构造完后，用prim算法求最小生成树即可。
这个题的输入处理有点问题。。不能用getchar()，我是参考了别人的代码改成这样才AC
getchar()---------->char temp[51];
gets(temp);
#include <stdio.h> #include <algorithm> #include <string.h> #include <queue> using namespace std; const int N = 200; const int INF = 9999999999; char a[N][N]; bool vis[N][N]; int graph[N][N]; int dis[N][N]; int n,m,k; struct Point { int x,y; } p[N*2]; void input(int &k) { for(int i=0; i<n; i++){ gets(a[i]); for(int j=0; j<m; j++){ if(a[i][j]==‘S‘){ p[0].x = i; p[0].y = j; } if(a[i][j]==‘A‘){ p[k].x =i; p[k++].y =j; } } } for(int i=0;i<k;i++){ for(int j=0;j<k;j++) graph[i][j] = INF; } } void BFS(Point start,int start1){ int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; memset(vis,false,sizeof(vis)); memset(dis,0,sizeof(dis)); queue<Point> q; q.push(start); vis[start.x][start.y] = true; while(!q.empty()){ Point t = q.front(); q.pop(); for(int i=0;i<4;i++){ int x = t.x+dir[i][0]; int y = t.y+dir[i][1]; if(x<0||x>=n||y<0||y>=m||vis[x][y]||a[x][y]==‘#‘) continue; dis[x][y]= dis[t.x][t.y]+1; vis[x][y] = true; Point p1; p1.x = x,p1.y = y; q.push(p1); } } for(int i=0;i<k;i++){ graph[start1][i] = dis[p[i].x][p[i].y]; } return; } bool vis1[N*2]; int low[N*2]; int prim(int n,int pos){ memset(vis1,false,sizeof(vis1)); memset(low,0,sizeof(low)); for(int i=0;i<n;i++){ low[i] = graph[pos][i]; } int cost = 0; vis1[pos] = true; low[pos] = 0; for(int i=1;i<n;i++){ int Min = INF; for(int j=0;j<n;j++){ if(!vis1[j]&&Min>low[j]){ pos = j; Min = low[j]; } } cost += Min; vis1[pos] = true; for(int j=0;j<n;j++){ if(!vis1[j]&&low[j]>graph[pos][j]) low[j] = graph[pos][j]; } } return cost; } int main() { int tcase; scanf("%d",&tcase); while(tcase--) { scanf("%d%d",&m,&n); char temp[51]; gets(temp); k=1; input(k); for(int i=0;i<k;i++) BFS(p[i],i); printf("%d\n",prim(k,0)); } return 0; }
原文：http://www.cnblogs.com/liyinggang/p/5482872.html