POJ - 3026 Borg Maze（最小生成树，BFS+Prim算法）

POJ - 3026

本题给出一个迷宫，问从S点出发遍历所有的A点最短距离是多少

思路：对S点+所有A点进行一遍BFS求出最短距离，然后建图求最小生成树即可。

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int INF = 0x3f3f3f3f;
int e[110][110],vis[55][55],cnt[55][55];
char s[55][55];
int dir[4][2]={
    1,0,0,1,-1,0,0,-1};
int n,m,ans;
struct note
{
    int x,y,s;
}tt;
void bfs(int dx,int dy)
{
    memset(vis,0,sizeof vis);queue<note>q;q.push((note){
    dx,dy,0});vis[dx][dy]=1;while(!q.empty()){
    tt=q.front();q.pop();for(int i=0;i<4;i++){
    int xx=tt.x+dir[i][0];int yy=tt.y+dir[i][1];int ss=tt.s+1;if(xx<1||xx>n||yy<1||yy>m) continue;if(vis[xx][yy]||s[xx][yy]=='#') continue;vis[xx][yy]=1;if(cnt[xx][yy]>0) //结点是A或者Se[cnt[dx][dy]][cnt[xx][yy]]=ss;q.push((note){
    xx,yy,ss});}}
}
int book[110],dis[110];
int prim(int s)
{
    memset(book,0,sizeof(book));for(int i=1;i<=ans;i++) dis[i]=e[1][i]; dis[s]=0;book[s]=1;int sum=0;for(int i=1;i<=ans-1;i++){
    int u,minn=INF;for(int j=1;j<=ans;j++)if(!book[j]&&dis[j]<minn){
    minn=dis[j];u=j;}book[u]=1;sum+=minn;for(int j=1;j<=ans;j++)dis[j]=min(dis[j],e[u][j]);}return sum;
}
int main()
{
    int t;scanf("%d",&t);while(t--){
    scanf("%d%d",&m,&n);gets(s[0]);for(int i=1;i<=n;i++) gets(s[i]+1);memset(cnt,0,sizeof(cnt));ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(s[i][j]=='A'||s[i][j]=='S')cnt[i][j]=++ans;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(cnt[i][j]>0)bfs(i,j);printf("%d\n",prim(1));		}return 0;
}