题目大意：
给你一个地图，求由地图上S点到其他点A的最短路径。
代码操作步骤：
1、记录下所有的A和S的位置。
2、BFS求出任意两点之间的最短路程，建立邻接矩阵。
3、Prim算法求最小生成树。
下面是代码：
#include <stdio.h> #include <string.h> #include <queue> using namespace std; const int M=105; struct node1 { int x,y,cut,in; } node[M],du,dc; bool map2[M][M][M]; int map1[M][M],n,x,y; char s[55][55]; #define typec int // type of cost const typec inf = 0x3f3f3f3f; // max of cost int vis[M]; typec lowc[M]; int find1(int x,int y) { for(int i=0; i<n; i++) { if(node[i].x==x&&node[i].y==y) { return i; } } } void bfs() { int i; memset(map2,0,sizeof(map2)); queue <struct node1> qu; for(i=0; i<n; i++) { qu.push(node[i]); map1[i][i]=0; map2[node[i].x][node[i].y][i]=1; } while(!qu.empty()) { du=qu.front(); qu.pop(); if(du.x>0&&s[du.x-1][du.y]!='#'&&!map2[du.x-1][du.y][du.in]) { dc.x=du.x-1; dc.y=du.y; dc.cut=du.cut+1; dc.in=du.in; if(s[du.x-1][du.y]=='S'||s[du.x-1][du.y]=='A') { map1[du.in][find1(du.x-1,du.y)]=dc.cut; } qu.push(dc); map2[du.x-1][du.y][du.in]=1; } if(du.x+1<y&&s[du.x+1][du.y]!='#'&&!map2[du.x+1][du.y][du.in]) { dc.x=du.x+1; dc.y=du.y; dc.cut=du.cut+1; dc.in=du.in; if(s[du.x+1][du.y]=='S'||s[du.x+1][du.y]=='A') { map1[du.in][find1(du.x+1,du.y)]=dc.cut; } qu.push(dc); map2[du.x+1][du.y][du.in]=1; } if(du.y>0&&s[du.x][du.y-1]!='#'&&!map2[du.x][du.y-1][du.in]) { dc.x=du.x; dc.y=du.y-1; dc.cut=du.cut+1; dc.in=du.in; if(s[du.x][du.y-1]=='S'||s[du.x][du.y-1]=='A') { map1[du.in][find1(du.x,du.y-1)]=dc.cut; } qu.push(dc); map2[du.x][du.y-1][du.in]=1; } if(du.y+1<x&&s[du.x][du.y+1]!='#'&&!map2[du.x][du.y+1][du.in]) { dc.x=du.x; dc.y=du.y+1; dc.cut=du.cut+1; dc.in=du.in; if(s[du.x][du.y+1]=='S'||s[du.x][du.y+1]=='A') { map1[du.in][find1(du.x,du.y+1)]=dc.cut; } qu.push(dc); map2[du.x][du.y+1][du.in]=1; } } } typec prim(typec cost[][M]) // vertex: 0 ~ n-1 { int i, j, p; typec minc, res = 0; memset(vis, 0, sizeof(vis)); vis[0] = 1; for (i=1; i<n; i++) { lowc[i] = cost[0][i]; } for (i=1; i<n; i++) { minc = inf; p = -1; for (j=0; j<n; j++) { if (0 == vis[j] && minc > lowc[j]) { minc = lowc[j]; p = j; } } res+=minc; vis[p] = 1; for (j=0; j<n; j++) { if (0 == vis[j] && lowc[j] > cost[p][j]) { lowc[j] = cost[p][j]; } } } return res; } int main() { int i,j,t; scanf("%d",&t); while(t--) { n=0; char temp[200]; scanf("%d%d",&x,&y); gets(temp); for(i=0; i<y; i++) { gets(s[i]); } for(i=0; i<y; i++) { for(j=0; j<x; j++) { if(s[i][j]=='A'||s[i][j]=='S') { node[n].x=i; node[n].y=j; node[n].in=n; node[n].cut=0; n++; } } } bfs(); printf("%d\n",prim(map1)); } return 0; }
转载于:https://www.cnblogs.com/lin375691011/p/3996820.html
相关资源：POJ3026-Borg Maze【BFS Prim】