POJ 3026 Borg Maze(BFS+最小生成树）
分类：
题目链接：?id=3026
本题可以把S与A视为一样的点，因为根据最小生成树的性质，，起点在哪都一样。然后每一点到其余点的距离用BFS搜索得到，在搜索过程中将距离用矩阵的形式存储起来。然后在得到所有距离后，用prim算法将最小生成树求出。
代码如下：
#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#include <ctype.h>#include<algorithm>using namespace std;int n, m, a[60][60], map[110][110], d[110], vis1[110][110], vis[110], maxint=100000, num;char st[60][60];int jx[]={0,0,1,-1};int jy[]={1,-1,0,0};struct node{int x, y, ans;}fei[10000000];void bfs(int x, int y, int q){int i, j, s=0, e=0, xx=0;node f1, f2;f1.x=x;f1.y=y;f1.ans=0;fei[s++]=f1;vis1[x][y]=1;while(s>e){f1=fei[e++];if(a[f1.x][f1.y]!=0&&a[f1.x][f1.y]!=q){map[q][a[f1.x][f1.y]]=map[a[f1.x][f1.y]][q]=f1.ans;xx++;if(xx==num-1){return ;}}for(i=0;i<4;i++){f2.x=f1.x+jx[i];f2.y=f1.y+jy[i];if(f2.x>=0&&f2.x<n&&f2.y>=0&&f2.y<m&&!vis1[f2.x][f2.y]&&(st[f1.x][f1.y]==’A’||st[f1.x][f1.y]==’S’||st[f1.x][f1.y]==’ ‘)){vis1[f2.x][f2.y]=1;f2.ans=f1.ans+1;fei[s++]=f2;}}}return ;}void prim(){int ans=0, i, j, pos, min1;for(i=2;i<=num;i++){d[i]=map[1][i];}vis[1]=1;for(i=1;i<num;i++){min1=maxint;for(j=2;j<=num;j++){if(!vis[j]&&min1>d[j]){min1=d[j];pos=j;}}vis[pos]=1;ans+=min1;for(j=2;j<=num;j++){if(!vis[j]&&d[j]>map[pos][j]){d[j]=map[pos][j];}}}printf("%d\n",ans);}int main(){int t, i, j, k, p, q;scanf("%d",&t);while(t–){scanf("%d%d ",&m,&n);k=1;memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));num=0;for(i=0; i<n; i++){gets(st[i]);for(j=0; j<m; j++){if(st[i][j]==’A’||st[i][j]==’S’){a[i][j]=k++;num++;}}}for(i=1;i<=num;i++){for(j=1;j<=num;j++){map[i][j]=maxint;}}for(i=0; i<n; i++){for(j=0; j<m; j++){if(a[i][j]){memset(vis1,0,sizeof(vis1));q=a[i][j];bfs(i,j,q);}}}prim();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇POJ 1679 The Unique MST 次小生成树下一篇GCJ Round1A Charging Chaos
再长的路，一步步也能走完，再短的路，不迈开双脚也无法到达。
